The Floyd-Warshall Algorithm is a dynamic programming-based graph algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It can handle negative edge weights but not negative cycles. This algorithm is widely used in networking, route optimization, and transitive closure problems due to its simplicity and efficiency for dense graphs.
Understanding the Problem
The challenge in Floyd-Warshall is iteratively updating a distance matrix so that dist[i][j] represents the shortest distance between vertices i and j. For each vertex k, the algorithm checks if including k as an intermediate vertex provides a shorter path between all pairs (i, j). Care must be taken to correctly initialize the distance matrix and handle cases with no direct edge.
Program 1: Floyd-Warshall Algorithm
This program demonstrates the Floyd-Warshall Algorithm to find the shortest distances between all pairs of vertices in a graph represented by an adjacency matrix. The algorithm systematically considers each vertex as an intermediate point to update the shortest paths.
#include <stdio.h>
#include <limits.h>
#define V 4
#define INF 99999
// Function to print the distance matrix
void printSolution(int dist[V][V]) {
printf("Shortest distances between every pair of vertices:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
// Floyd-Warshall Algorithm function
void floydWarshall(int graph[V][V]) {
int dist[V][V];
// Initialize distance matrix same as input graph
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
// Update distances using all vertices as intermediate
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
int main() {
int graph[V][V] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}The Floyd-Warshall algorithm works by iteratively considering each vertex as an intermediate node in paths between all pairs of vertices. By updating the distance matrix using these intermediate vertices, it ensures that the shortest paths between every pair are computed efficiently. This method is particularly useful for dense graphs and for computing all-pairs shortest paths in a single run.
Program 2: Floyd-Warshall Algorithm Using Adjacency Matrix (Dynamic Memory)
This version uses dynamic memory to handle graphs of variable size. It works similarly to the original matrix version but is more flexible for larger graphs.
#include <stdio.h>
#include <stdlib.h>
#define INF 99999
// Function to print distance matrix
void printSolution(int **dist, int V) {
printf("Shortest distances between every pair of vertices:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
// Floyd-Warshall algorithm
void floydWarshall(int **graph, int V) {
int **dist = (int**) malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
dist[i] = (int*) malloc(V * sizeof(int));
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
}
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
printSolution(dist, V);
for (int i = 0; i < V; i++) free(dist[i]);
free(dist);
}
int main() {
int V = 4;
int **graph = (int**) malloc(V * sizeof(int*));
int temp[V][V] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
for (int i = 0; i < V; i++) {
graph[i] = (int*) malloc(V * sizeof(int));
for (int j = 0; j < V; j++)
graph[i][j] = temp[i][j];
}
floydWarshall(graph, V);
for (int i = 0; i < V; i++) free(graph[i]);
free(graph);
return 0;
}This dynamic memory version allows handling larger graphs without hardcoding the size, making it flexible for user-defined inputs.
Program 3: Floyd-Warshall Algorithm Using Adjacency List (Sparse Graphs)
This program demonstrates Floyd-Warshall adapted for adjacency lists. It avoids storing a full matrix, which is memory-efficient for sparse graphs.
#include <stdio.h>
#include <stdlib.h>
#define INF 99999
typedef struct Node {
int vertex;
int weight;
struct Node *next;
} Node;
typedef struct Graph {
int V;
Node **adjLists;
} Graph;
// Create a new adjacency node
Node* createNode(int v, int w) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->vertex = v;
newNode->weight = w;
newNode->next = NULL;
return newNode;
}
// Create graph
Graph* createGraph(int V) {
Graph *graph = (Graph*) malloc(sizeof(Graph));
graph->V = V;
graph->adjLists = (Node**)malloc(V * sizeof(Node*));
for (int i = 0; i < V; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Add edge (directed)
void addEdge(Graph *graph, int src, int dest, int weight) {
Node *newNode = createNode(dest, weight);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// Print solution
void printSolution(int **dist, int V) {
printf("Shortest distances (Adjacency List):\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) printf("%7s", "INF");
else printf("%7d", dist[i][j]);
}
printf("\n");
}
}
// Floyd-Warshall using adjacency list
void floydWarshall(Graph *graph) {
int V = graph->V;
int **dist = (int**) malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
dist[i] = (int*) malloc(V * sizeof(int));
for (int j = 0; j < V; j++)
dist[i][j] = (i == j ? 0 : INF);
Node *temp = graph->adjLists[i];
while (temp) {
dist[i][temp->vertex] = temp->weight;
temp = temp->next;
}
}
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
printSolution(dist, V);
for (int i = 0; i < V; i++) free(dist[i]);
free(dist);
}
int main() {
int V = 4;
Graph *graph = createGraph(V);
addEdge(graph, 0, 1, 5);
addEdge(graph, 0, 3, 10);
addEdge(graph, 1, 2, 3);
addEdge(graph, 2, 3, 1);
floydWarshall(graph);
for (int i = 0; i < V; i++) {
Node *temp = graph->adjLists[i];
while (temp) {
Node *toFree = temp;
temp = temp->next;
free(toFree);
}
}
free(graph->adjLists);
free(graph);
return 0;
}Using adjacency lists, the algorithm efficiently handles sparse graphs by storing only existing edges. The distance matrix is built dynamically from the lists, and the standard Floyd-Warshall updates are applied. This approach saves memory when most vertex pairs are not directly connected.
FAQs
Q1: What is the time complexity of Floyd-Warshall?
O(V³), where V is the number of vertices.
Q2: Can it handle negative edge weights?
Yes, but not negative cycles.
Q3: Is Floyd-Warshall suitable for sparse graphs?
It is less efficient for sparse graphs due to O(V³) complexity; Dijkstra or Bellman-Ford may be better.
Q4: How to detect negative cycles?
After running the algorithm, if dist[i][i] < 0 for any i, the graph contains a negative cycle.
Conclusion
Floyd-Warshall Algorithm provides a simple and effective way to compute shortest paths between all pairs of vertices in weighted graphs. Its dynamic programming approach guarantees correct results and is particularly useful in dense graphs and applications requiring complete shortest path information.
References & Additional Resources
A collection of books and online tutorials providing theory and practical examples for understanding the Floyd-Warshall algorithm and graph algorithms in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language, 2nd Edition. Prentice Hall – Classic reference on C fundamentals, including pointers, memory, and algorithm implementation.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Covers graph representations, shortest path algorithms, and their C implementations.
- Programiz: Floyd-Warshall Algorithm – Step-by-step explanation with C code examples.
- Tutorialspoint: All-Pairs Shortest Path Algorithms – Detailed guide on the Floyd-Warshall algorithm and its applications.
