shortest paths

If interested in shortest paths for all pairs of nodes, use Floyd-Warshall.

If the graph is sparse, use Dijkstra’s.

If the graph has negative weights, use Bellman-Ford.

bellman-ford algorithm §

time: O(VE)

• V-1 iterations to relax E edges

space: O(V)

SPFA §

time: $\Theta (E)$, O(VE)

space: O(V+E)

dijkstra’s algorithm §

time: O((V+E) log V)

• making the graph: O(E)
• popping vertices: O(V log V)
• pushing edges: O(E log V)

space: O(V+E)

floyd-warshall algorithm §

time: O($V^3$)

space: O($V^2$)