the Floyd-Warshall algorithm

Floyd-Warshall fills the entire all-pairs distance table with one of the most elegant short programs in computer science: three nested loops. The idea is to grow the set of cities you are allowed to pass through. First find best routes that use no intermediate city, then routes allowed to pass through city 1, then through cities 1 or 2, and so on. Each time you permit one more city as a stopover, you ask whether routing through it shortens any pair's distance.

Keep a matrix D where D[i][j] is the current best distance from i to j, initialized to the direct edge weight (or infinity, with 0 on the diagonal). Then loop k from 1 to V, and inside it loop over all i and all j, applying the single update D[i][j] = min(D[i][j], D[i][k] + D[k][j]). The meaning of the outer index is a dynamic-programming layering: after the iteration for a given k, D[i][j] is the shortest path from i to j using only intermediate vertices drawn from {1, ..., k}. The induction is clean — for the next k+1, any path through intermediates up to k+1 either avoids k+1 (already counted) or passes through it once, splitting into i-to-(k+1) and (k+1)-to-j pieces that use only earlier intermediates, exactly the two terms being summed. After k reaches V, every vertex is an allowed stopover and D holds true shortest distances. The cost is a clean O(V^3) in time and O(V^2) space.

Its appeal is simplicity and generality: a handful of lines, it handles NEGATIVE edge weights fine, and it computes every pair at once, which is why it is a favorite for small dense graphs and competitive programming. It also detects negative cycles — if any diagonal entry D[i][i] becomes negative, a negative cycle passes through i. The honest limits: O(V^3) is too slow for large sparse graphs (Johnson's V-Dijkstra approach wins there), and it needs the full V^2 matrix in memory, so it does not scale to millions of vertices.