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