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
Graphclass 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
1to 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)
)


