In this exercise, we will port a JavaScript implementation of the Floyd-Warshall algorithm to Python.
This algorithm computes the shortest path between any node and any other node in a directed graph with integral edge lengths.
We are given:
- Several test cases
- A complete JavaScript implementation
- A partial Python implementation (a
Graph
class and file I/O)
We need to write the floyd_warshall
function, so that it passes as many of the test cases as possible. The function should return the smallest of all the computed shortest paths for a given graph, or "NULL"
if the graph contains a negative cycle.
We are given the following graph:
3 5
1 2 -3
1 2 1
2 3 -1
3 1 1
3 2 3
The first line tells us that the graph has 3 nodes and 5 edges. Each subsequent line represents an edge (e.g. 1 2 -3
is an edge from node 1
to node 2
with an edge length of -3).
- What's the shortest path from node
1
to node2
? - Does this graph have a negative cycle?
Floyd-Warshall works by constraining the nodes we allow to be along the path from a node i
to a node j
using a third index, k
. For example, a value of k = 5
means that only the set of nodes {1, 2, 3, 4, 5}
are allowed along the path from i
to j
.
Say i = 17
, j = 10
and k = 5
. In the example below, the shortest path is clearly the bottom two edges. But we have the constraint k
is at most 5
. This constraint only applies to nodes in the middle of the path, but the bottom path uses 7
. That path is disallowed. Therefore the shortest path from 17
to 10
given this constraint would be the three-edge path on top, which has the bigger length of 3
.
let A = 3-D array indexed by i, j, k
# Base Case
for all i,j in V:
A[i,j,0] = {
0 if i = j
e_ij if (i, j) in E
+Infinity if i != j and (i, j) not in E
# Main Loop
for k = 1 to n
for i = 1 to n
for j = 1 to n
A[i, j, k] = min(
A[i, j, k - 1] # (case 1)
A[i, k, k - 1] + A[k, j, k - 1] # (case 2)
)