Compute the shortest distances between every pair of nodes in a weighted directed graph.
Implement the function `floyd_warshall(num_nodes, edges)` that computes the shortest path distances between all pairs of nodes in a directed weighted graph.
The graph has nodes numbered from `0` to `num_nodes - 1`. The input is a list of `edges`, where each edge is a tuple `(u, v, weight)`. This represents a directed edge from node `u` to node `v` with the given integer `weight` (can be negative). The graph is guaranteed to have NO negative cycles (i.e., no cycle with total weight less than zero).
If two nodes are unreachable, the distance is `None`. Distances from a node to itself are `0` (even if there is a self-loop, the shortest is 0).
Your function should return a 2D list (list of lists) `dist` such that `dist[i][j]` is the shortest distance from node `i` to node `j`, or `None` if no path exists.
The graph may be large, so use the Floyd-Warshall algorithm with O(n^3) time and O(n^2) space.
Constraints
- 1 <= num_nodes <= 300
- 0 <= len(edges) <= 10000
- Each edge: 0 <= u, v < num_nodes, weight is an integer, |weight| <= 10^6
- No negative cycles in the graph.
- The returned matrix must have exactly `num_nodes` rows and `num_nodes` columns.
Example
>>> num_nodes = 4
>>> edges = [(0, 1, 3), (1, 2, -2), (0, 2, 5), (2, 3, 1)]
>>> floyd_warshall(num_nodes, edges)
[[0, 3, 1, 2], [None, 0, -2, -1], [None, None, 0, 1], [None, None, None, 0]]
>>> num_nodes = 3
>>> edges = [(0, 1, 1), (0, 2, 4), (1, 2, 2)]
>>> floyd_warshall(num_nodes, edges)
[[0, 1, 3], [None, 0, 2], [None, None, 0]]
>>> num_nodes = 2
>>> edges = [(1, 0, 5)]
>>> floyd_warshall(num_nodes, edges)
[[0, None], [5, 0]]
25 points
~30 min