Given a 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 every source s for all vertices v present in the graph. If the graph contains negative-weight cycle, report it.

For example, consider below input graph –

**Output:**

Adjacency matrix containing shortest distance is –

0 -1 -2 0

4 0 2 4

5 1 0 2

3 -1 1 0

Shortest Path from vertex 0 to vertex 1 is (0 2 3 1)

Shortest Path from vertex 0 to vertex 2 is (0 2)

Shortest Path from vertex 0 to vertex 3 is (0 2 3)

Shortest Path from vertex 1 to vertex 0 is (1 0)

Shortest Path from vertex 1 to vertex 2 is (1 0 2)

Shortest Path from vertex 1 to vertex 3 is (1 0 2 3)

Shortest Path from vertex 2 to vertex 0 is (2 3 1 0)

Shortest Path from vertex 2 to vertex 1 is (2 3 1)

Shortest Path from vertex 2 to vertex 3 is (2 3)

Shortest Path from vertex 3 to vertex 0 is (3 1 0)

Shortest Path from vertex 3 to vertex 1 is (3 1)

Shortest Path from vertex 3 to vertex 2 is (3 1 0 2)

We have already covered **single-source shortest paths** in separate posts. We have seen that

- For graphs having non-negative edge weights,
**Dijkstra’s algorithm**runs in O(E + V lg V) - For graphs containing negative edge weights,
**Bellman-Ford**runs in O(V.E). - For a DAG, one pass of Bellman-Ford
*(called relaxation step)*is enough that will take O(V + E) time.

Here, V is number of vertices and E is number of edges in the graph.

In this post, we will introduce **All-Pairs Shortest Paths **that returns the shortest paths between every of vertices in graph that can contain negative edge weights.

If the graph contains only positive edge weights, a simple solution would be to run Dijkstra’s algorithm V times. The time complexity of this solution would be O(V(E + V lg V)) i.e. O(VE + V^{2} lg V)

If the graph contains negative edge weights, then to find all-pairs shortest paths we can run Bellman-Ford once from each vertex. The time complexity of this approach will be O(V^{2}E). If the graph is dense i.e. E = V^{2}, then the time complexity becomes O(V^{4}).

**Floyd–Warshall algorithm** is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). It does so by comparing all possible paths through the graph between each pair of vertices and that too with O(V^{3}) comparisons in a graph.

Below is the psedocode for Bellman-Ford as given in wikipedia. The implementation takes in a graph, represented by adjacency matrix and fills dist[] with shortest-path (least cost) information –

let dist be a V x V matrix of minimum distances initialized to infinity

for each vertex v

dist[v][v] = 0

for each edge (u, v)

dist[u][v] = weight(u,v)

for k from 0 to |V| – 1

for i from 0 to |V| – 1

for j from 0 to |V| – 1

if (dist[i][k] + dist[k][j]) is less than dist[i][j] then

dist[i][j] = dist[i][k] + dist[k][j]

Above psedocode picks a vertex k from 0 to V-1 one by one and include that vertex as an intermediate vertex in the shortest path between every pair of edges i->j in the graph. We update the cost matrix whenever we found a shorter path from i to j through vertex k. Since for a given k, we have already considered vertices [0..k-1] as intermediate vertices, this approach works.

Let’s consider above graph,

Before first iteration of the outer for loop for k, the only known paths corresponds to the single edges in the graph.

**At k = 0, paths that go through the vertex 0 are found**: in particular, the path [1, 0, 2] is found, replacing the path [1, 2] which has fewer edges but is costly.

**At k = 1, paths going through the vertices {0, 1} are found**. The below figure shows how the path [3, 1, 0, 2] is assembled from the two known paths [3, 1] and [1, 0, 2] encountered in previous iterations, with 1 in the intersection. The path [3, 1, 2] is not considered, because [1, 0, 2] is the shortest path encountered so far from 1 to 2.

**At k = 2, paths going through the vertices {0, 1, 2} are found.**

**Finally, at k = 3, all shortest paths are found.**

The Floyd–Warshall algorithm is very simple to code and really efficient in practice. It can also be used to for finding the **transitive closure** of graph and **detecting negative weight cycles in the graph. **

To detect negative cycles using the Floyd–Warshall algorithm, we need to the check diagonal of the distance matrix for presence of a negative number as it indicates that the graph contains at least one negative cycle.

**How this works?**

The Floyd–Warshall algorithm iteratively revises path lengths between all pairs of vertices (i, j), including where i = j. Initially, the length of the path (i, i) is zero. A path [i, k…i] can only improve upon this if it has length less than zero, i.e. denotes a negative cycle. Thus, after the algorithm, (i, i) will be negative if there exists a negative-length path from i back to i.

**C++ implementation –**

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 122 123 124 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the adjMatrix #define N 4 // Recurive Function to print path of given // vertex u from source vertex v void printPath(int path[][N], int v, int u) { if (path[v][u] == v) return; printPath(path, v, path[v][u]); cout << path[v][u] << " "; } // Function to print the shortest cost with path // information between all pairs of vertices void printSolution(int cost[N][N], int path[N][N]) { for (int v = 0; v < N; v++) { for (int u = 0; u < N; u++) { if (cost[v][u] == INT_MAX) cout << setw(5) << "inf"; else cout << setw(5) << cost[v][u]; } cout << endl; } cout << endl; for (int v = 0; v < N; v++) { for (int u = 0; u < N; u++) { if (u != v && path[v][u] != -1) { cout << "Shortest Path from vertex " << v << " to vertex " << u << " is (" << v << " "; printPath(path, v, u); cout << u << ")" << endl; } } } } // Function to run Floyd-Warshell algorithm void FloydWarshell(int adjMatrix[][N]) { // cost[] and parent[] stores shortest-path // (shortest-cost/shortest route) information int cost[N][N], path[N][N]; // initialize cost[] and parent[] for (int v = 0; v < N; v++) { for (int u = 0; u < N; u++) { // initally cost would be same as weight // of the edge cost[v][u] = adjMatrix[v][u]; if (v == u) path[v][u] = 0; else if (cost[v][u] != INT_MAX) path[v][u] = v; else path[v][u] = -1; } } // run Floyd-Warshell for (int k = 0; k < N; k++) { for (int v = 0; v < N; v++) { for (int u = 0; u < N; u++) { // If vertex k is on the shortest path from v to u, // then update the value of cost[v][u], path[v][u] if (cost[v][k] != INT_MAX && cost[k][u] != INT_MAX && cost[v][k] + cost[k][u] < cost[v][u]) { cost[v][u] = cost[v][k] + cost[k][u]; path[v][u] = path[k][u]; } } // if diagonal elements become negative, the // graph contains a negative weight cycle if (cost[v][v] < 0) { cout << "Negative Weight Cycle Found!!"; return; } } } // Print the shortest path between all pairs of vertices printSolution(cost, path); } // main function int main() { // given adjacency representation of matrix int adjMatrix[N][N] = { { 0, INT_MAX, -2, INT_MAX }, { 4, 0, 3, INT_MAX }, { INT_MAX, INT_MAX, 0, 2 }, { INT_MAX, -1, INT_MAX, 0 } }; // Run Floyd Warshell algorithm FloydWarshell(adjMatrix); return 0; } |

**Output: **

Adjacency matrix containing shortest distance is –

0 -1 -2 0

4 0 2 4

5 1 0 2

3 -1 1 0

Shortest Path from vertex 0 to vertex 1 is (0 2 3 1)

Shortest Path from vertex 0 to vertex 2 is (0 2)

Shortest Path from vertex 0 to vertex 3 is (0 2 3)

Shortest Path from vertex 1 to vertex 0 is (1 0)

Shortest Path from vertex 1 to vertex 2 is (1 0 2)

Shortest Path from vertex 1 to vertex 3 is (1 0 2 3)

Shortest Path from vertex 2 to vertex 0 is (2 3 1 0)

Shortest Path from vertex 2 to vertex 1 is (2 3 1)

Shortest Path from vertex 2 to vertex 3 is (2 3)

Shortest Path from vertex 3 to vertex 0 is (3 1 0)

Shortest Path from vertex 3 to vertex 1 is (3 1)

Shortest Path from vertex 3 to vertex 2 is (3 1 0 2)

**Time complexity** of Floyd–Warshall algorithm is O(V^{3}) where V is number of vertices in the graph.

**Johnson’s algorithm** can also be used to find the shortest paths between all pairs of vertices in a sparse, weighted, directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It uses the Bellman–Ford algorithm to transform the input graph such that it removes all negative weights from the graph and run Dijkstra’s algorithm on the transformed graph.

**References:**

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

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