bellman ford Algorithm
The Bellman-Ford algorithm is a graph-based algorithm that solves the single-source shortest path problem, which is used to find the shortest paths from a source vertex to all other vertices in a weighted, directed graph. Developed independently by Richard Bellman and Lester Ford in the late 1950s, the algorithm works by iteratively refining the distance estimates to each vertex and guarantees convergence to the correct solution after a certain number of iterations. The key feature of the Bellman-Ford algorithm is its ability to handle negative weight edges, making it particularly useful in situations where the edge weights can represent costs, time, or other quantities that may have negative values.
The algorithm operates by initializing the distance estimates to all vertices except the source vertex to infinity, and then iteratively updating the distance estimates by relaxing each edge. Relaxation refers to the process of testing whether the current distance estimate to a vertex can be improved by considering an alternative path through an intermediate vertex. The algorithm performs the relaxation step for each edge in the graph, repeating this process for a total of |V|-1 iterations, where |V| represents the number of vertices in the graph. After these iterations, the algorithm guarantees that the distance estimates represent the shortest paths from the source vertex to all other vertices, unless there exists a negative weight cycle in the graph. In such cases, the Bellman-Ford algorithm can detect the negative cycle, thus indicating that no solution exists for the shortest path problem.
//
// BellmanFord algorithm implementation in C++
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/cpp/graphs/bellman-ford/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Nikunj Taneja
// Github: @underscoreorcus
//
#include <bits/stdc++.h>
struct Edge
{
int src, dest, weight;
};
struct Graph
{
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
// Step 1: Initialize distances from src to all other vertices
// as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple shortest
// path from src to any other vertex can have at-most |V| - 1
// edges
for (int i = 1; i <= V-1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// Step 3: check for negative-weight cycles. The above step
// guarantees shortest distances if graph doesn't contain
// negative weight cycle. If we get a shorter path, then there
// is a cycle.
for (int i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle");
}
printArr(dist, V);
return;
}
int main()
{
/* Sample graph */
int V = 5;
int E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}
