Floyd-Warshall Algorithm in C – All-Pairs Shortest Paths

Floyd-Warshall algorithm finds the shortest paths between every pair of vertices in a weighted graph in a single O(V³) pass. While Dijkstra’s algorithm starts from one source vertex, Floyd-Warshall answers the all-pairs problem: “what is the shortest path from vertex i to vertex j for every i and j?” It uses dynamic programming — systematically trying every vertex as a potential intermediate stop and updating the distance table when a shorter route is found. It handles negative-weight edges and can detect negative-weight cycles. This page gives a working C implementation, a step-by-step trace of how the distance matrix evolves, and path reconstruction using a next-hop table.

The Core Idea — Try Every Intermediate Vertex

The Floyd-Warshall recurrence is:

dist[i][j] = min(dist[i][j],  dist[i][k] + dist[k][j])

Read it as: “can we get from i to j more cheaply by going via k first?” The algorithm loops k from 0 to V−1, and for each k it checks every (i, j) pair. After the outer loop finishes with k=V−1, the table holds the globally optimal distances because every possible intermediate vertex has been considered.

Step-by-Step Trace (4-Vertex Example)

Graph edges (undirected): 0–1 weight 3, 0–2 weight 8, 0–3 weight 7, 1–2 weight 2, 2–3 weight 1.

Adjacency matrix (0 = no edge):
     0   1   2   3
0  [ 0   3   8   7 ]
1  [ 3   0   2   0 ]
2  [ 8   2   0   1 ]
3  [ 7   0   1   0 ]

Initial dist matrix (INF where no direct edge):

     0   1   2   3
0  [ 0   3   8   7 ]
1  [ 3   0   2  INF]
2  [ 8   2   0   1 ]
3  [ 7  INF  1   0 ]

After k=0 (use vertex 0 as intermediate):

• dist[1][3] = min(INF, 3+7=10) → 10. Path now known: 1→0→3.
• dist[3][1] = min(INF, 7+3=10) → 10. Path: 3→0→1.

After k=1 (use vertex 1 as intermediate):

• dist[0][2] = min(8, 3+2=5) → 5. Path: 0→1→2 beats direct 0→2=8.
• dist[2][0] = min(8, 2+3=5) → 5. Symmetric update.

After k=2 (use vertex 2 as intermediate):

• dist[0][3] = min(7, 5+1=6) → 6. Path: 0→1→2→3 beats direct 0→3=7.
• dist[1][3] = min(10, 2+1=3) → 3. Path: 1→2→3.
• dist[3][0] = min(7, 1+5=6) → 6. Symmetric.
• dist[3][1] = min(10, 1+2=3) → 3. Path: 3→2→1.

After k=3: No further improvements. Final matrix:

     0   1   2   3
0  [ 0   3   5   6 ]
1  [ 3   0   2   3 ]
2  [ 5   2   0   1 ]
3  [ 6   3   1   0 ]

Notice dist[0][3]=6 (path 0→1→2→3) is cheaper than the direct edge 0→3=7. Floyd-Warshall found the better route automatically.

C Program: Floyd-Warshall Algorithm

/* Floyd-Warshall all-pairs shortest path algorithm
 * Compile: gcc -ansi -Wall -Wextra floydw.c -o floydw */
#include <stdio.h>
#define MAX 10
#define INF 1000000

/* Print the path from i to j by following next-hop pointers. */
void print_path(int nxt[][MAX], int i, int j)
{
    printf("%d", i);
    while (i != j) {
        if (nxt[i][j] == -1) { printf(" ... (no path)"); return; }
        i = nxt[i][j];
        printf(" -> %d", i);
    }
}

void floyd_warshall(int graph[][MAX], int n)
{
    int dist[MAX][MAX], nxt[MAX][MAX];
    int i, j, k, via;

    /* Initialise from the raw edge weights */
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0;   nxt[i][j] = i;
            } else if (graph[i][j] > 0) {
                dist[i][j] = graph[i][j];
                nxt[i][j]  = j;   /* direct edge: next hop is j itself */
            } else {
                dist[i][j] = INF; nxt[i][j] = -1;
            }
        }
    }

    /* Core DP: try each vertex k as an intermediate stop */
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) continue;
                via = dist[i][k] + dist[k][j];
                if (via < dist[i][j]) {
                    dist[i][j] = via;
                    nxt[i][j]  = nxt[i][k]; /* first hop toward k */
                }
            }
        }
    }

    /* Print distance matrix */
    printf("All-pairs shortest distance matrix:\n");
    printf("     ");
    for (j = 0; j < n; j++) printf("%6d", j);
    printf("\n     ");
    for (j = 0; j < n; j++) printf("------");
    printf("\n");
    for (i = 0; i < n; i++) {
        printf("%3d |", i);
        for (j = 0; j < n; j++) {
            if (dist[i][j] == INF) printf("   INF");
            else printf("%6d", dist[i][j]);
        }
        printf("\n");
    }

    /* Print every shortest path */
    printf("\nShortest paths:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i == j) continue;
            printf("  %d -> %d (dist %d):  ", i, j, dist[i][j]);
            if (dist[i][j] == INF) printf("no path");
            else print_path(nxt, i, j);
            printf("\n");
        }
    }
}

int main(void)
{
    int graph[MAX][MAX];
    int n, i, j;

    printf("Enter number of vertices (2-%d): ", MAX);
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX) {
        printf("Invalid.\n"); return 1;
    }
    printf("Enter %dx%d adjacency matrix (0 = no edge):\n", n, n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (scanf("%d", &graph[i][j]) != 1) {
                printf("Invalid.\n"); return 1;
            }

    floyd_warshall(graph, n);
    return 0;
}

Sample Output

Enter number of vertices (2-10): 4
Enter 4x4 adjacency matrix (0 = no edge):
0 3 8 7
3 0 2 0
8 2 0 1
7 0 1 0

All-pairs shortest distance matrix:
          0     1     2     3
     ------------------------
  0 |     0     3     5     6
  1 |     3     0     2     3
  2 |     5     2     0     1
  3 |     6     3     1     0

Shortest paths:
  0 -> 1 (dist 3):  0 -> 1
  0 -> 2 (dist 5):  0 -> 1 -> 2
  0 -> 3 (dist 6):  0 -> 1 -> 2 -> 3
  1 -> 3 (dist 3):  1 -> 2 -> 3
  3 -> 0 (dist 6):  3 -> 2 -> 1 -> 0
  ...

Code Explanation

• dist[i][j]: The shortest known distance from vertex i to vertex j. Starts as the raw edge weight (or INF if no direct edge). Updated whenever going via some intermediate k yields a shorter total.
• nxt[i][j]: The next vertex to visit when travelling the shortest path from i to j. Initialize to j for a direct edge (first hop is the destination itself). When a route via k is shorter, set nxt[i][j] = nxt[i][k] — the first step toward k becomes the first step toward j. Following nxt pointers from any source traces the full path to any destination.
• The triple loop: The outer loop variable k is the candidate intermediate vertex — “can going via k help?” The inner two loops (i, j) test all source-destination pairs. After iteration k, every path that benefits from routing through vertex k is already optimal for all vertices 0..k. After all V iterations, the table is globally optimal.
• The guard dist[i][k] == INF || dist[k][j] == INF: If k is unreachable from i (or j is unreachable from k), using k as an intermediate is meaningless. This guard also prevents integer overflow from adding two large INF values.
• print_path() — iterative walk: Starting at i, jump to nxt[i][j], then from there to nxt[next][j], and so on until the current vertex equals j. The loop always terminates because every step brings us closer to j along the known shortest path.

Comparison: Floyd-Warshall vs Dijkstra vs Bellman-Ford

Property	Floyd-Warshall	Dijkstra (once)	Bellman-Ford (once)
Problem solved	All-pairs shortest paths	Single-source shortest paths	Single-source shortest paths
Time complexity	O(V³)	O(V²) with matrix	O(V·E)
Space	O(V²)	O(V)	O(V)
Negative edges	Yes	No	Yes
Negative cycles	Detects (diagonal < 0)	N/A	Detects
Path reconstruction	nxt[][] matrix	parent[] array	parent[] array

Use Floyd-Warshall when you need all-pairs distances or when the graph has negative edges. Use Dijkstra when you have one source and all edge weights are non-negative. To run Dijkstra V times for all-pairs, the total cost is O(V³) — the same as Floyd-Warshall — but Floyd-Warshall’s constant factor is smaller and the code is simpler.

Detecting Negative Cycles

After the algorithm finishes, check dist[i][i] for every vertex i. If any diagonal entry is negative, the graph contains a negative-weight cycle (a cycle whose total weight is less than zero). This makes shortest paths undefined for vertices that can reach the cycle, because you could loop indefinitely to reduce the cost. In practice, add this check after the main DP loop:

for (i = 0; i < n; i++)
    if (dist[i][i] < 0) {
        printf("Negative cycle detected.\n");
        return;
    }

Frequently Asked Questions

Related Programs

• Dijkstra’s Algorithm in C – Shortest Path
• Prim’s Algorithm in C – Minimum Spanning Tree
• BFS in C – Breadth-First Search
• DFS in C – Depth-First Search

Recommended books:
The C Programming Language — K&R (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice graph algorithm questions: C Aptitude Questions — or try our C Programming Quiz App on Android.