All-pairs shortest paths (Undirected)

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

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3	Shimbel algorithm (1953)
Cubic	Floyd–Warshall algorithm (1962) Seidel's algorithm (1995) Williams 2014 (2014) Pettie & Ramachandran 2002 (2002) Zwick, Uri 2008 (2008) Chan 2009 (2009)
Quadratic	Thorup 1999 (1999)
nlogn
Linear
logn