Floyd-Warshall¶
1def floyd_warshall(n, edges): # Floyd-Warshall algorithm
2 dist = [[float('inf')] * n for _ in range(n)] # Initialize matrix
3 for i in range(n):
4 dist[i][i] = 0 # Distance to self is zero
5 for u, v, w in edges:
6 dist[u][v] = w # Assign edge weights
7
8 for k in range(n):
9 for i in range(n):
10 for j in range(n):
11 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) # Relaxation step
12 return dist
The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted directed graph. This algorithm works even with graphs containing negative weight edges, provided there are no negative cycles. Its main idea is to gradually improve the shortest path estimates between all pairs through intermediate vertices.
The time complexity of the algorithm is \(O(n^3)\) and its space complexity is \(O(n^2)\), making it suitable for dense graphs where the number of vertices n is relatively small. By modifying the condition in the relaxation step to dist[i][k] and dist[k][j] instead of summing, the algorithm can also be used to determine reachability between all pairs of vertices (transitive closure).
Problem Statement¶
We have a directed weighted graph \(G\) . The weights of the edges in \(G\) can also be negative. We know that graph \(G\) contains no cycles with negative total weight.
In this problem, for every pair of vertices \((u, v)\), we want the length of the shortest path from \(u\) to \(v\). The length of a path is equal to the sum of its edge weights.
Floyd-Warshall Algorithm¶
To solve this problem, we first define a \(dp\) with dimensions \(|V(G)|.|V(G)|.|V(G)|\) where \(dp_{k, i, j}\) equals the length of the shortest walk from vertex \(i\) to vertex \(j\), where the intermediate vertices (vertices in the path except \(i\) and \(j\) themselves) are chosen from the set \(\lbrace 1, 2, \dots, k \rbrace\).
We know that the length of the shortest walk between two vertices in graph \(G\) is equal to the length of the shortest path. This is because if the shortest walk contains a repeated vertex, it implies the existence of a cycle with positive length (according to the problem's assumption, cycles cannot have negative lengths). This cycle can be removed to obtain a shorter walk, leading to a contradiction.
For the base cases of this dp, we know that \(dp_{0, i, i} = 0\). For any pair of vertices \((u, v)\), we set \(dp_{0, u, v}\) equal to the weight of the shortest edge from \(u\) to \(v\) (if no edge exists between \(u\) and \(v\), then \(dp_{0, u, sc} = \infty\)).
To compute \(dp_{k, i, j}\), we consider two cases: 1. Vertex \(k\) is not in the optimal path. In this case, the answer is \(dp_{k - 1, i, j}\). 2. Vertex \(k\) is in the path. Here, the optimal path length is \(dp_{k - 1, i, k} + dp_{k - 1, k, j}\), since we first travel from \(i\) to \(k\) and then from \(k\) to \(j\). In both subpaths, the intermediate vertices are guaranteed to have indices less than \(k\).
The length of the shortest path from vertex \(u\) to vertex \(v\) is given by the value of \(dp_{n, u, v}\).
Order Analysis¶
For updating each DP cell, we perform \(\mathcal{O}(1)\) operations. We know the DP has a complexity of \(\mathcal{O}\left(\left|V\left(G\right)\right|^{3}\right)\). Thus, in total, we perform \(\mathcal{O}\left(\left|V\left(G\right)\right|^{3}\right)\) operations. The memory order used is also \(\mathcal{O}\left(\left|V\left(G\right)\right|^{3}\right)\).
Memory Order Optimization¶
To optimize the memory consumption, we can remove the first dimension. As a result, the memory order complexity becomes \(\mathcal{O}\left(\left|V\left(G\right)\right|^{2}\right)\).
The idea is to create a \(for\) loop from 1 to \(\left|V\left(G\right)\right|\) and name its variable \(k\). Then, in each iteration, update every cell of the \(dp\) array. By "updating", we mean branching based on whether vertex \(k\) is part of the intermediate vertices in the path, similar to the standard approach.
To prove correctness, we assert that after each iteration of the first loop, all values remain valid. Initially, we note that any \(dp\) cell with one of its dimensions equal to \(k\) will never change. When updating other \(dp\) cells, we use values from cells that necessarily have \(k\) as one of their dimensions.
Thus, by induction, we can prove that after the \(k\)-th iteration, \(dp_{i, j} = dp^{\prime}_{k, i, j}\) where \(dp^{\prime}\) is the non-optimized version of the DP array. After the \(n\)-th iteration, we will obtain the desired values.
By induction, it can be proven that after the \(k\)-th iteration, \(dp_{i, j} = dp^{\prime}_{k, i, j}\) where \(dp^{\prime}\) is the non-optimized DP array. Hence, after the \(n\)-th iteration, we will achieve the target values.
Negative Cycle¶
You may wonder, if it is not guaranteed whether the graph has a negative cycle or not, how can we determine if a negative cycle exists? For this purpose, we first set \(dp_{i, i} = 0\). If during the execution of the algorithm, any entry \(dp_{i, i} < 0\) becomes true, then we know there exists a closed walk of negative length from \(i\) to \(i\), and we know that every closed walk with negative length contains a cycle of negative length.
If a negative cycle exists, then for some vertex \(u\) in that negative cycle, it must satisfy \(dp_{u, u} < 0\). This is because, according to the definition of \(dp\), the negative cycle will correctly propagate its effect to \(dp_{u, u}\) and make it negative.
Based on the above two arguments, the existence of a negative cycle is equivalent to having \(dp_{i, i} < 0\). Thus, it is sufficient to check whether any \(dp_{i, i}\) becomes negative during the process.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
