The Bellman-Ford Algorithm is a graph-based algorithm that computes the shortest path from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s Algorithm, it can handle negative edge weights, making it suitable for scenarios where some connections have penalties or costs. Bellman-Ford is widely used in network routing, transportation planning, and systems with variable or negative edge costs, and it can also detect negative weight cycles, which indicate that no finite shortest path exists.
Understanding the Problem
The main challenge in implementing Bellman-Ford is correctly iterating through all edges repeatedly to relax distances. Relaxation involves updating the shortest known distance to a vertex if a shorter path is found. After |V| – 1 iterations (V = number of vertices), the algorithm also checks for negative weight cycles, which can make shortest path calculations invalid.
Program 1: Bellman-Ford Algorithm
This program demonstrates the Bellman-Ford Algorithm using an edge list representation. It computes the shortest distances from a source vertex to all other vertices, even if some edges have negative weights.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 5 // Number of vertices
#define E 8 // Number of edges
typedef struct Edge {
int src, dest, weight;
} Edge;
// Function to print the distance array
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
// Bellman-Ford Algorithm function
void bellmanFord(Edge edges[], int src) {
int dist[V];
// Initialize distances to all vertices as infinite
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Relax all edges |V| - 1 times
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int w = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
// Check for negative weight cycles
for (int j = 0; j < E; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int w = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
printf("Graph contains negative weight cycle\n");
return;
}
}
printSolution(dist);
}
int main() {
Edge edges[E] = {
{0, 1, -1}, {0, 2, 4},
{1, 2, 3}, {1, 3, 2},
{1, 4, 2}, {3, 2, 5},
{3, 1, 1}, {4, 3, -3}
};
int source = 0;
printf("Bellman-Ford shortest paths from vertex %d:\n", source);
bellmanFord(edges, source);
return 0;
}Bellman-Ford relaxes each edge |V| – 1 times, ensuring that all shortest paths are found from the source vertex. After these iterations, it checks for negative weight cycles to prevent incorrect calculations. This algorithm works even with negative edge weights, unlike Dijkstra’s algorithm, making it suitable for a wider range of weighted graphs.
Program 2: Bellman-Ford Algorithm Using Adjacency List
This program demonstrates Bellman-Ford using an adjacency list representation, storing only existing edges. It computes shortest paths from a source vertex and detects negative weight cycles.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
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 a graph with V vertices
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 directed edge
void addEdge(Graph *graph, int src, int dest, int weight) {
Node *newNode = createNode(dest, weight);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// Bellman-Ford algorithm using adjacency list
void bellmanFord(Graph *graph, int src) {
int V = graph->V;
int *dist = (int*) malloc(V * sizeof(int));
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Relax edges |V| - 1 times
for (int i = 1; i <= V - 1; i++) {
for (int u = 0; u < V; u++) {
Node *temp = graph->adjLists[u];
while (temp) {
int v = temp->vertex;
int w = temp->weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
temp = temp->next;
}
}
}
// Check for negative weight cycles
for (int u = 0; u < V; u++) {
Node *temp = graph->adjLists[u];
while (temp) {
int v = temp->vertex;
int w = temp->weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
printf("Graph contains negative weight cycle\n");
free(dist);
return;
}
temp = temp->next;
}
}
// Print distances
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
free(dist);
}
int main() {
int V = 5;
Graph *graph = createGraph(V);
addEdge(graph, 0, 1, -1);
addEdge(graph, 0, 2, 4);
addEdge(graph, 1, 2, 3);
addEdge(graph, 1, 3, 2);
addEdge(graph, 1, 4, 2);
addEdge(graph, 3, 2, 5);
addEdge(graph, 3, 1, 1);
addEdge(graph, 4, 3, -3);
printf("Bellman-Ford shortest paths from vertex 0:\n");
bellmanFord(graph, 0);
// Free memory
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, Bellman-Ford efficiently handles sparse graphs, as only existing edges are stored. Distances are updated iteratively by relaxing edges, and negative cycles are detected by checking if any edge can still reduce a distance after |V| – 1 iterations.
FAQs
Q1: What is the time complexity of Bellman-Ford?
O(V * E), where V is the number of vertices and E is the number of edges.
Q2: Can Bellman-Ford handle negative edges?
Yes, unlike Dijkstra’s Algorithm, it can handle negative edge weights.
Q3: How does it detect negative weight cycles?
By checking if further relaxation is possible after |V| – 1 iterations.
Q4: Is Bellman-Ford suitable for large graphs?
It works but may be slower than Dijkstra’s Algorithm for dense graphs because of its higher time complexity.
Conclusion
Bellman-Ford Algorithm is an essential graph algorithm for finding shortest paths in graphs that may contain negative edge weights. Understanding its relaxation technique and cycle detection makes it a powerful tool in network routing and optimization problems.
References & Additional Resources
These books and online resources provide both theoretical explanations and practical examples for understanding the Bellman-Ford 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.
- GeeksforGeeks: Bellman-Ford Algorithm in C – Step-by-step explanation with example code.
- Programiz: Bellman-Ford Algorithm – Beginner-friendly guide with clear C examples.
