Floyd's Algorithm
Floyd's algorithm (Floyd-Warshall) finds the shortest paths between all pairs of vertices in a weighted graph using dynamic programming.
Introduction
Floyd's Algorithm (Floyd-Warshall Algorithm) is a dynamic programming algorithm for finding the shortest paths between all pairs of vertices in a weighted graph. Proposed by Robert Floyd in 1962, it efficiently handles both directed and undirected graphs and can detect negative cycles.
Problem Statement
Given a weighted directed graph G = (V, E), compute the shortest path distance between every pair of vertices (i, j) in the graph.
Real World Applications
- → Computing routing tables in computer networks
- → Finding transitive closure of a graph
- → Detecting negative cycles in financial models
- → Geographic mapping — all-city distance computation
- → Scheduling and dependency analysis
Algorithm Explanation
Floyd's algorithm uses a 2D distance matrix dist[i][j]. It considers each vertex k as an intermediate vertex and checks: is the path from i to j through k shorter than the direct path? If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j]. After considering all intermediate vertices, the matrix contains all-pairs shortest path distances.
Step-by-Step Procedure
- 1 Initialize dist[i][j] with the given adjacency matrix (use INFI for no direct edge).
- 2 For each intermediate vertex k from 1 to n:
- 3 For each source vertex i from 1 to n:
- 4 For each destination vertex j from 1 to n:
- 5 If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j].
- 6 After all iterations, dist[i][j] contains the shortest path from i to j.
- 7 Print the final distance matrix.
Complete C Program
#include<stdlib.h>
#include<stdio.h>
#define MAX 10
#define min(c,d) (c < d ? c : d)
int dist[MAX][MAX], n;
void floyd() {
int i, j, k;
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main() {
int i, j;
printf("Enter the Number of Vertices: ");
scanf("%d", &n);
printf("Enter the Distance Matrix (99 for no edge):\n");
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &dist[i][j]);
floyd();
printf("Shortest Distance Matrix:\n");
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++)
printf("%4d", dist[i][j]);
printf("\n");
}
return 0;
}Sample Input & Output
4
0 3 99 7
3 0 2 99
99 2 0 1
7 99 1 0Shortest Distance Matrix:
0 3 5 6
3 0 2 3
5 2 0 1
6 3 1 0Dry Run / Trace
Initial matrix with 4 vertices. k=1: Check paths through vertex 1. Update dist[2][4]=min(99,3+7)=10, dist[4][2]=10. k=2: dist[1][3]=min(99,3+2)=5, dist[3][1]=5, dist[1][4]=min(7,3+99)=7, dist[4][1]=7. k=3: dist[1][4]=min(7,5+1)=6, dist[2][4]=min(10,2+1)=3. k=4: dist[1][2]=min(3,6+3)=3. Final matrix shows all shortest paths.
Advantages & Disadvantages
✓ Advantages
- + Computes all-pairs shortest paths in one pass
- + Simple three-nested-loop implementation
- + Handles negative edge weights (but not negative cycles)
- + Can detect negative cycles
✗ Disadvantages
- − O(V³) time complexity — not suitable for very large graphs
- − O(V²) space for distance matrix
- − Only gives distances, not the actual paths (needs modification)
Viva Questions & Answers
Q1. What is the principle behind Floyd's algorithm?
Dynamic programming: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate vertex k.
Q2. How can you detect a negative cycle using Floyd's algorithm?
After running the algorithm, if dist[i][i] < 0 for any vertex i, there is a negative cycle.
Q3. What is the difference between Floyd's and Dijkstra's algorithm?
Floyd's solves all-pairs shortest paths in O(V³). Dijkstra's solves single-source shortest paths in O(V²) or O(E log V) with a heap.
Q4. Can Floyd's algorithm handle negative edge weights?
Yes, Floyd's algorithm works with negative edge weights, but fails if there are negative weight cycles.
Q5. How to reconstruct the actual path using Floyd's algorithm?
Maintain a predecessor matrix next[i][j]. Initialize next[i][j] = j. When dist[i][j] is updated via k, set next[i][j] = next[i][k].