All-pairs shortest paths (Undirected)
Jump to navigation
Jump to search
Problem Description
It aims to figure out the shortest path from each vertex v to every other u. Storing all the paths explicitly can be very memory expensive indeed, as we need one spanning tree for each vertex. This is often impractical regarding memory consumption, so these are generally considered as all pairs-shortest distance problems, which aim to find just the distance from each to each node to another. We usually want the output in tabular form: the entry in u's row and v's column should be the weight of the shortest path from u to v.
Bounds Chart
Error creating thumbnail: Unable to save thumbnail to destination
Step Chart
Error creating thumbnail: Unable to save thumbnail to destination
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | Shimbel algorithm (1953) | |
| Cubic | Floyd–Warshall algorithm (1962) | |
| Quadratic | Thorup 1999 (1999) | |
| nlogn | ||
| Linear | ||
| logn |