Floyd Warshall All Pairs Shortest Path in DSA C

Mental Model

Find the shortest path between every pair of points by checking if going through a middle point is better.

Analogy: Imagine you want to find the quickest way to travel between every pair of cities by trying all possible stopovers to see if they save time.

  [0] -> [1] -> [2]
   ↑      ↑      ↑
  dist  dist  dist
  matrix shows shortest distances between nodes

Dry Run Walkthrough

Input: Graph with 3 nodes and edges: 0->1=4, 0->2=11, 1->2=2

Goal: Find shortest distances between all pairs of nodes

Step 1: Initialize distance matrix with direct edges and 0 for same nodes

dist = [[0,4,11], [∞,0,2], [∞,∞,0]]

Why: Start with known direct distances and zero for self to build upon

Step 2: Use node 0 as intermediate to update distances

dist = [[0,4,11], [∞,0,2], [∞,∞,0]]

Why: Check if going through node 0 improves any path (none here)

Step 3: Use node 1 as intermediate to update distances

dist = [[0,4,6], [∞,0,2], [∞,∞,0]]

Why: Path 0->2 updated from 11 to 6 via 1 (4 + 2)

Step 4: Use node 2 as intermediate to update distances

dist = [[0,4,6], [∞,0,2], [∞,∞,0]]

Why: No further improvements found using node 2

Result:

dist = [[0,4,6], [∞,0,2], [∞,∞,0]]
Shortest distances between all pairs found

Annotated Code

DSA C

#include <stdio.h>
#define V 3
#define INF 99999

void floydWarshall(int graph[V][V]) {
    int dist[V][V], i, j, k;

    // Initialize distance matrix same as input graph
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Update distances considering each vertex as intermediate
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Print the shortest distance matrix
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("INF ");
            else
                printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {
        {0, 4, 11},
        {INF, 0, 2},
        {INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

dist[i][j] = graph[i][j];

copy initial distances from input graph to dist matrix

if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {

check if path through k is shorter than current dist[i][j]

dist[i][j] = dist[i][k] + dist[k][j];

update dist[i][j] to shorter path via k

Output

0 4 6 

INF 0 2 

INF INF 0 

Complexity Analysis

Time: O(V^3) because we check all pairs (i,j) for each intermediate node k

Space: O(V^2) because we store distances between all pairs in a matrix

vs Alternative: Compared to running Dijkstra from each node (O(V * E log V)), Floyd Warshall is simpler but slower for sparse graphs

Edge Cases

Graph with no edges except self loops

Distances remain zero for self loops and INF for others

DSA C

dist[i][j] = graph[i][j];

Graph with negative edge weights but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA C

if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {

Graph with negative cycles

Algorithm does not detect negative cycles; distances may become incorrect

DSA C

No explicit guard; Floyd Warshall needs extra check for negative cycles

When to Use This Pattern

When asked to find shortest paths between all pairs of nodes in a graph, especially with negative edges but no negative cycles, use Floyd Warshall to systematically check all intermediate nodes.

Common Mistakes

Mistake: Not initializing the distance matrix correctly from the input graph
Fix: Copy the input graph distances into the dist matrix before starting updates

Mistake: Not checking for INF before adding distances, causing integer overflow
Fix: Add condition to skip updates if intermediate distances are INF

Mistake: Confusing the order of loops, which breaks the algorithm logic
Fix: Use the correct triple nested loop order: for k, for i, for j

Summary

Finds shortest paths between every pair of nodes by considering all possible intermediate nodes.

Use when you need all pairs shortest paths, especially with graphs that may have negative edges but no negative cycles.

The key insight is that any shortest path can be built by combining shorter paths through intermediate nodes.