Floyd-Warshall
All-pairs shortest-paths algorithm — computes the shortest path between every pair of nodes. Robert Floyd / Stephen Warshall (1962).
Beautiful DP formulation: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every intermediate node k. Three nested loops, 8 lines of code. Time complexity O(V³) — impractical on large graphs but perfect for <200 nodes.
Powers routing tables in small networks, transitive closure, "shortest handshake between two people in a social graph". Handles negative weights (but not negative cycles). Competitor: Johnson's algorithm (V·E·logV, better on sparse graphs).