Given a source vertex s from set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph. If the graph contains negative-weight cycle, report it.

For example, consider below graph

`Output:`

Distance of vertex 0 from the source is 0. It's path is [ 0 ]

Distance of vertex 1 from the source is -1. It's path is [ 0 -> 1 ]

Distance of vertex 2 from the source is 2. It's path is [ 0 -> 1 -> 2 ]

Distance of vertex 3 from the source is -2. It's path is [ 0 -> 1 -> 4 -> 3 ]

Distance of vertex 4 from the source is 1. It's path is [ 0 -> 1 -> 4 ]

The idea is to use Bellman–Ford algorithm to compute the shortest paths from a single source vertex to all of the other vertices in given weighted digraph. Bellman–Ford algorithm is slower than Dijkstra’s Algorithm but it is capable of handling negative weights edges in the graph unlike Dijkstra’s.

Note that if a graph contains a “negative cycle” (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no shortest path. Any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. Bellman–Ford algorithm can easily detect any negative cycles in the graph.

The algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration i that the edges are scanned, the algorithm finds all shortest paths of at most length i edges. Since the longest possible path without a cycle can be `V-1` edges, the edges must be scanned `V-1` times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length `|V|` edges has been found which can only occur if at least one negative cycle exists in the graph.

Below is the psedocode for Bellman-Ford as per wikipedia. The implementation takes in a graph, represented as lists of vertices and edges, and fills `distance[]` and `parent[]` with shortest-path (least cost/path) information –

function BellmanFord(list vertices, list edges, vertex source,

distance[], parent[])

// Step 1 – initialize graph. At the beginning, all vertices have a weight of

// infinity and a null parent, except for the Source, where the weight is 0

for each vertex v in vertices

distance[v] = INFINITY

parent[v] = NULL

distance[source] = 0

// Step 2 – relax edges repeatedly

for i = 1 to V-1 // V – No. of vertices

for each edge (u, v) with weight w

if distance[u] + w && distance[v]

distance[v] = distance[u] + w

parent[v] = u

// Step 3 – check for negative-weight cycles

for each edge (u, v) with weight w in edges

if (distance[u] + w) is less than distance[v]

return “Graph contains a negative-weight cycle”

return distance[], parent[]

Below slideshow illustrates the working of Bellman Ford Algorithm. The images are taken from MIT 6.046J/18.401J Introduction to Algorithms (Lecture 18 by Prof. Erik Demaine).

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include <iostream> #include <vector> #include <iomanip> #include <climits> using namespace std; // Data structure to store graph edges struct Edge { int source, dest, weight; }; // Recurive Function to print path of given vertex v from source vertex void printPath(vector<int> const &parent, int v) { if (v < 0) return; printPath(parent, parent[v]); cout << v << " "; } // Function to run Bellman Ford Algorithm from given source void BellmanFord(vector<Edge> const &edges, int source, int N) { // count number of edges present in the graph int E = edges.size(); // distance[] and parent[] stores shortest-path (least cost/path) // information. Initially all vertices except source vertex have // a weight of infinity and a no parent vector<int> distance (N, INT_MAX); distance[source] = 0; vector<int> parent (N, -1); int u, v, w, k = N; // Relaxation step (run V-1 times) while (--k) { for (int j = 0; j < E; j++) { // edge from u to v having weight w u = edges[j].source, v = edges[j].dest; w = edges[j].weight; // if the distance to the destination v can be // shortened by taking the edge u-> v if (distance[u] != INT_MAX && distance[u] + w < distance[v]) { // update distance to the new lower value distance[v] = distance[u] + w; // set v's parent as u parent[v] = u; } } } // Run Relaxation step once more for Nth time to // check for negative-weight cycles for (int i = 0; i < E; i++) { // edge from u to v having weight w u = edges[i].source, v = edges[i].dest; w = edges[i].weight; // if the distance to the destination u can be // shortened by taking the edge u-> v if (distance[u] != INT_MAX && distance[u] + w < distance[v]) { cout << "Negative Weight Cycle Found!!"; return; } } for (int i = 0; i < N; i++) { cout << "Distance of vertex " << i << " from the source is " << setw(2) << distance[i] << ". It's path is [ "; printPath(parent, i); cout << "]" << '\n'; } } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { // (x, y, w) -> edge from x to y having weight w { 0, 1, -1 }, { 0, 2, 4 }, { 1, 2, 3 }, { 1, 3, 2 }, { 1, 4, 2 }, { 3, 2, 5 }, { 3, 1, 1 }, { 4, 3, -3 } }; // Set maximum number of nodes in the graph int N = 5; // let source be vertex 0 int source = 0; // run Bellman Ford Algorithm from given source BellmanFord(edges, source, N); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
import java.util.*; // Data structure to store graph edges class Edge { int source, dest, weight; public Edge(int source, int dest, int weight) { this.source = source; this.dest = dest; this.weight = weight; } }; class BellmanFord { // Recursive Function to print path of given vertex v from source vertex static void printPath(int parent[], int v) { if (v < 0) return; printPath(parent, parent[v]); System.out.print(v + " "); } // Function to run Bellman Ford Algorithm from given source public static void BellmanFord(List<Edge> edges, int source, int N) { // get number of edges present in the graph int E = edges.size(); // distance[] and parent[] stores shortest-path // (least cost/path) information int distance[] = new int[N]; int parent[] = new int[N]; // initialize distance[] and parent[]. Initially all // vertices except source vertex have a weight of // infinity and a no parent Arrays.fill(distance, Integer.MAX_VALUE); distance[source] = 0; Arrays.fill(parent, -1); int k = N; // Relaxation step (run V -1 times) while (--k > 0) { for (int j = 0; j < E; j++) { // edge from u to v having weight w int u = edges.get(j).source; int v = edges.get(j).dest; int w = edges.get(j).weight; // if the distance to the destination v can be // shortened by taking the edge u-> v if (distance[u] != Integer.MAX_VALUE && (distance[u] + w < distance[v])) { // update distance to the new lower value distance[v] = distance[u] + w; // set v's parent as u parent[v] = u; } } } // run relaxation step once more for Nth time to // check for negative-weight cycles for (int i = 0; i < E; i++) { // edge from u to v having weight w int u = edges.get(i).source; int v = edges.get(i).dest; int w = edges.get(i).weight; // if the distance to the destination u can be // shortened by taking the edge u-> v if (distance[u] != Integer.MAX_VALUE && (distance[u] + w < distance[v])) { System.out.println("Negative Weight Cycle Found!!"); return; } } for (int i = 0; i < N; i++) { System.out.print("Distance of vertex " + i + " from the " + "source is " + distance[i] + ". It's path is [ "); printPath(parent, i); System.out.println("]"); } } public static void main(String[] args) { // vector of graph edges as per above diagram List<Edge> edges = Arrays.asList( // (x, y, w) -> edge from x to y having weight w new Edge( 0, 1, -1 ), new Edge( 0, 2, 4 ), new Edge( 1, 2, 3 ), new Edge( 1, 3, 2 ), new Edge( 1, 4, 2 ), new Edge( 3, 2, 5 ), new Edge( 3, 1, 1 ), new Edge( 4, 3, -3 ) ); // Number of vertices in the graph final int N = 5; // let source be vertex 0 int source = 0; // run Bellman Ford Algorithm from given source BellmanFord(edges, source, N); } } |

`Output:`

Distance of vertex 0 from the source is 0. It’s path is [ 0 ]

Distance of vertex 1 from the source is -1. It’s path is [ 0 1 ]

Distance of vertex 2 from the source is 2. It’s path is [ 0 1 2 ]

Distance of vertex 3 from the source is -2. It’s path is [ 0 1 4 3 ]

Distance of vertex 4 from the source is 1. It’s path is [ 0 1 4 ]

The time complexity of Bellman–Ford algorithm is `O(VE)` where V and E are the number of vertices and edges in the graph respectively.

**References:**

1. https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

2. MIT. Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 18 Prof. Erik Demaine

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

How can I put a constain on the number of edges, you are allowed to cross?

Hey guys what about global sequence alignment. can i get some information about this problem?