Floyd-Warshall Algorithm – Complete Notes

With Code, Example, Diagrams & Applications

Floyd-Warshall Algorithm – Complete Notes

With Code, Example, Diagrams & Applications

Floyd-Warshall Algorithm – Complete Notes

With Code, Example, Diagrams & Applications

1. What is Floyd-Warshall Algorithm?

Finds shortest paths between ALL PAIRS of vertices in a weighted graph (with or without negative edges).

  • Dynamic Programming approach.
  • Works with negative weights (but no negative cycles).
  • Computes a distance matrix dist[i][j] = shortest path from i to j.

2. Key Idea

"Can going via an intermediate vertex k reduce the path from i to j?"

dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )
  • Try all possible intermediate vertices k = 0 to V-1.
  • Order of k doesn't matter → all paths considered.

3. Algorithm Steps

1. Initialize dist[][]:
   dist[i][j] = weight(i,j) if edge exists
   dist[i][i] = 0
   dist[i][j] = ∞ if no direct edge

2. For k = 0 to V-1:
      For i = 0 to V-1:
         For j = 0 to V-1:
            if dist[i][k] + dist[k][j] < dist[i][j]:
               dist[i][j] = dist[i][k] + dist[k][j]
               path[i][j] = path[i][k]  // for path reconstruction

3. Check for negative cycles:
   If dist[i][i] < 0 for any i → Negative cycle exists

4. Example Graph

    A ──4──► B
    │       ↗
    2      3
    ↓     ↙
    D ◄──1── C
       -2

Adjacency Matrix (Initial)

A B C D
A 0 4 ∞ 2
B ∞ 0 3 ∞
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

5. Step-by-Step Execution

k = 0 (via A)

i\j A B C D
A 0 4 ∞ 2
B ∞ 0 3 ∞
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

→ No updates (no path i→A→j shorter)

k = 1 (via B)

Check i→B→j:

  • A→B→C: 4 + 3 = 7 < ∞ → Update A→C = 7
  • No other improvements

After k=1:

A B C D
A 0 4 7 2
B ∞ 0 3 ∞
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

k = 2 (via C)

Check i→C→j:

  • A→C→B: 7 + 1 = 8 > 4 → No
  • A→C→D: 7 + (-2) = 5 > 2 → No
  • B→C→D: 3 + (-2) = 1 < ∞ → Update B→D = 1
  • C→C→D: -2 → already 0

After k=2:

A B C D
A 0 4 7 2
B ∞ 0 3 1
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

k = 3 (via D)

Check i→D→j: Only D→D = 0 → No updates

Final Distance Matrix:

A B C D
A 0 4 7 2
B ∞ 0 3 1
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

6. Final Shortest Paths

From \ To A B C D
A 0 4 7 2
B ∞ 0 3 1
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

7. Full C Code Implementation

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

void floydWarshall(int graph[V][V]) {
    int dist[V][V], path[V][V];

    // Initialize
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
            if (i == j) path[i][j] = -1;
            else if (graph[i][j] != INF) path[i][j] = i;
            else path[i][j] = -1;
        }
    }

    // Floyd-Warshall core
    for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
            for(int 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];
                    path[i][j] = path[k][j];
                }
            }
        }
    }

    // Check negative cycle
    for(int i = 0; i < V; i++) {
        if (dist[i][i] < 0) {
            printf("Negative cycle detected!\n");
            return;
        }
    }

    // Print result
    printf("All-Pairs Shortest Paths:\n");
    printf("   ");
    for(int i = 0; i < V; i++) printf("%c  ", 'A' + i);
    printf("\n");

    for(int i = 0; i < V; i++) {
        printf("%c  ", 'A' + i);
        for(int j = 0; j < V; j++) {
            if (dist[i][j] == INF) printf("INF ");
            else printf("%3d ", dist[i][j]);
        }
        printf("\n");
    }

    // Print path example: A to D
    printf("\nPath from A to D:\n");
    int start = 0, end = 3;
    printf("%c ", 'A' + start);
    while (start != end) {
        int next = path[start][end];
        if (next == -1) {
            printf("→ No path\n");
            break;
        }
        printf("→ %c ", 'A' + next);
        start = next;
    }
    if (start == end) printf("→ %c\n", 'A' + end);
}

// Main
int main() {
    int graph[V][V] = {
        {0,   4,   INF, 2},
        {INF, 0,   3,   INF},
        {INF, 1,   0,   -2},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

8. Output

All-Pairs Shortest Paths:
     A   B   C   D  
A    0   4   7   2 
B  INF   0   3   1 
C  INF   1   0  -2 
D  INF INF INF   0 

Path from A to D:
A → A → D

9. Time & Space Complexity

Metric Complexity
Time O(V³)
Space O(V²)

Best for dense graphs or small V (V ≤ 400)

10. Applications

Use Case Example
All-pairs routing Internet routing tables
Transitive closure Reachability in graphs
Arbitrage detection Currency exchange
Graph analysis Social networks
Game maps Shortest path between any two points

11. Negative Cycle Detection

if (dist[i][i] < 0) → Negative cycle!

Example:

A → B (1), B → C (-2), C → A (0) → Cycle weight = -1 < 0

12. Comparison: Floyd-Warshall vs Others

Algorithm Pairs Negative Edges Negative Cycle Time
Floyd-Warshall All Yes Yes O(V³)
Dijkstra (xV) All No No O(V(E + V log V))
Bellman-Ford (xV) All Yes Yes O(V²E)

Floyd-Warshall wins for dense graphs & small V

13. Path Reconstruction

Use path[i][j] matrix:

path[i][j] = last intermediate vertex on path i→j

Recursive Print:

void printPath(int path[][V], int i, int j) {
    if (path[i][j] == -1) return;
    printPath(path, i, path[i][j]);
    printf(" → %c", 'A' + path[i][j]);
    printPath(path, path[i][j], j);
}

14. Optimization Tips

  1. Use adjacency matrix (faster cache)
  2. Early exit if no updates in a k loop
  3. Bitset optimization for unweighted graphs

15. Summary Table

Feature Floyd-Warshall
Purpose All-pairs shortest paths
Time O(V³)
Space O(V²)
Negative Weights Yes
Negative Cycle Detects
Best for Dense graphs, V ≤ 400

16. Practice Problems

  1. Find shortest path between all pairs in a city map
  2. Detect arbitrage in currency exchange rates
  3. Compute transitive closure of a graph
  4. Optimize Floyd-Warshall with early termination
  5. Reconstruct all paths using path matrix

Key Takeaways

Floyd-Warshall = DP on 3D matrix
One algorithm → All pairs
O(V³) → Use only when V is small
Detects negative cycles

End of Notes

Last updated: Nov 12, 2025

Floyd-Warshall Algorithm – Complete Notes

With Code, Example, Diagrams & Applications

Floyd-Warshall Algorithm – Complete Notes

With Code, Example, Diagrams & Applications

Floyd-Warshall Algorithm – Complete Notes

With Code, Example, Diagrams & Applications

1. What is Floyd-Warshall Algorithm?

Finds shortest paths between ALL PAIRS of vertices in a weighted graph (with or without negative edges).

  • Dynamic Programming approach.
  • Works with negative weights (but no negative cycles).
  • Computes a distance matrix dist[i][j] = shortest path from i to j.

2. Key Idea

"Can going via an intermediate vertex k reduce the path from i to j?"

dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )
  • Try all possible intermediate vertices k = 0 to V-1.
  • Order of k doesn't matter → all paths considered.

3. Algorithm Steps

1. Initialize dist[][]:
   dist[i][j] = weight(i,j) if edge exists
   dist[i][i] = 0
   dist[i][j] = ∞ if no direct edge

2. For k = 0 to V-1:
      For i = 0 to V-1:
         For j = 0 to V-1:
            if dist[i][k] + dist[k][j] < dist[i][j]:
               dist[i][j] = dist[i][k] + dist[k][j]
               path[i][j] = path[i][k]  // for path reconstruction

3. Check for negative cycles:
   If dist[i][i] < 0 for any i → Negative cycle exists

4. Example Graph

    A ──4──► B
    │       ↗
    2      3
    ↓     ↙
    D ◄──1── C
       -2

Adjacency Matrix (Initial)

A B C D
A 0 4 ∞ 2
B ∞ 0 3 ∞
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

5. Step-by-Step Execution

k = 0 (via A)

i\j A B C D
A 0 4 ∞ 2
B ∞ 0 3 ∞
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

→ No updates (no path i→A→j shorter)

k = 1 (via B)

Check i→B→j:

  • A→B→C: 4 + 3 = 7 < ∞ → Update A→C = 7
  • No other improvements

After k=1:

A B C D
A 0 4 7 2
B ∞ 0 3 ∞
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

k = 2 (via C)

Check i→C→j:

  • A→C→B: 7 + 1 = 8 > 4 → No
  • A→C→D: 7 + (-2) = 5 > 2 → No
  • B→C→D: 3 + (-2) = 1 < ∞ → Update B→D = 1
  • C→C→D: -2 → already 0

After k=2:

A B C D
A 0 4 7 2
B ∞ 0 3 1
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

k = 3 (via D)

Check i→D→j: Only D→D = 0 → No updates

Final Distance Matrix:

A B C D
A 0 4 7 2
B ∞ 0 3 1
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

6. Final Shortest Paths

From \ To A B C D
A 0 4 7 2
B ∞ 0 3 1
C ∞ 1 0 -2
D ∞ ∞ ∞ 0

7. Full C Code Implementation

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

void floydWarshall(int graph[V][V]) {
    int dist[V][V], path[V][V];

    // Initialize
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
            if (i == j) path[i][j] = -1;
            else if (graph[i][j] != INF) path[i][j] = i;
            else path[i][j] = -1;
        }
    }

    // Floyd-Warshall core
    for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
            for(int 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];
                    path[i][j] = path[k][j];
                }
            }
        }
    }

    // Check negative cycle
    for(int i = 0; i < V; i++) {
        if (dist[i][i] < 0) {
            printf("Negative cycle detected!\n");
            return;
        }
    }

    // Print result
    printf("All-Pairs Shortest Paths:\n");
    printf("   ");
    for(int i = 0; i < V; i++) printf("%c  ", 'A' + i);
    printf("\n");

    for(int i = 0; i < V; i++) {
        printf("%c  ", 'A' + i);
        for(int j = 0; j < V; j++) {
            if (dist[i][j] == INF) printf("INF ");
            else printf("%3d ", dist[i][j]);
        }
        printf("\n");
    }

    // Print path example: A to D
    printf("\nPath from A to D:\n");
    int start = 0, end = 3;
    printf("%c ", 'A' + start);
    while (start != end) {
        int next = path[start][end];
        if (next == -1) {
            printf("→ No path\n");
            break;
        }
        printf("→ %c ", 'A' + next);
        start = next;
    }
    if (start == end) printf("→ %c\n", 'A' + end);
}

// Main
int main() {
    int graph[V][V] = {
        {0,   4,   INF, 2},
        {INF, 0,   3,   INF},
        {INF, 1,   0,   -2},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

8. Output

All-Pairs Shortest Paths:
     A   B   C   D  
A    0   4   7   2 
B  INF   0   3   1 
C  INF   1   0  -2 
D  INF INF INF   0 

Path from A to D:
A → A → D

9. Time & Space Complexity

Metric Complexity
Time O(V³)
Space O(V²)

Best for dense graphs or small V (V ≤ 400)

10. Applications

Use Case Example
All-pairs routing Internet routing tables
Transitive closure Reachability in graphs
Arbitrage detection Currency exchange
Graph analysis Social networks
Game maps Shortest path between any two points

11. Negative Cycle Detection

if (dist[i][i] < 0) → Negative cycle!

Example:

A → B (1), B → C (-2), C → A (0) → Cycle weight = -1 < 0

12. Comparison: Floyd-Warshall vs Others

Algorithm Pairs Negative Edges Negative Cycle Time
Floyd-Warshall All Yes Yes O(V³)
Dijkstra (xV) All No No O(V(E + V log V))
Bellman-Ford (xV) All Yes Yes O(V²E)

Floyd-Warshall wins for dense graphs & small V

13. Path Reconstruction

Use path[i][j] matrix:

path[i][j] = last intermediate vertex on path i→j

Recursive Print:

void printPath(int path[][V], int i, int j) {
    if (path[i][j] == -1) return;
    printPath(path, i, path[i][j]);
    printf(" → %c", 'A' + path[i][j]);
    printPath(path, path[i][j], j);
}

14. Optimization Tips

  1. Use adjacency matrix (faster cache)
  2. Early exit if no updates in a k loop
  3. Bitset optimization for unweighted graphs

15. Summary Table

Feature Floyd-Warshall
Purpose All-pairs shortest paths
Time O(V³)
Space O(V²)
Negative Weights Yes
Negative Cycle Detects
Best for Dense graphs, V ≤ 400

16. Practice Problems

  1. Find shortest path between all pairs in a city map
  2. Detect arbitrage in currency exchange rates
  3. Compute transitive closure of a graph
  4. Optimize Floyd-Warshall with early termination
  5. Reconstruct all paths using path matrix

Key Takeaways

Floyd-Warshall = DP on 3D matrix
One algorithm → All pairs
O(V³) → Use only when V is small
Detects negative cycles

End of Notes

Last updated: Nov 12, 2025