Floyd-Warshall (all-pairs shortest path)

Shortest distance between every pair of nodes at once, by letting each node in turn act as a stepping stone.

The idea

For every node k, check every pair (i, j): is the route from i to k to j shorter than the best route found so far from i to j directly? If so, routing through k is an improvement. After trying every node as a stepping stone, dist[i][j] holds the true shortest distance for every pair.

Code

public static int[,] FloydWarshall(int[,] dist, int n) {
    // dist[i, j] already holds direct edge weights, 0 on the diagonal, infinity otherwise
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i, k] + dist[k, j] < dist[i, j])
                    dist[i, j] = dist[i, k] + dist[k, j]; // shorter via k
    return dist;
}

Tips

• The triple loop order matters: k must be the outermost loop, since dist[i][k] and dist[k][j] must already reflect every stepping stone tried before k.
• It handles negative edges (not negative cycles) and, unlike running Dijkstra from every node, it works even when some edges are negative.

In the .NET library

A 2-D int[,] is a true rectangular array in C#; it is contiguous in memory and usually faster than an int[][] jagged array for a dense grid like this one.