All-pairs shortest paths by dynamic programming: allow one more node at a time as a possible stop-over, and for every pair ask whether going through it is shorter. Three nested loops over the nodes, nothing more.
- Average time
- O(V³)
- Space
- O(V²)
All-pairs shortest paths by dynamic programming: allow one more node at a time as a possible stop-over, and for every pair ask whether going through it is shorter. Three nested loops over the nodes, nothing more.