Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
Bellman-Ford Algorithm
Bellman Ford algorithm helps us find the shortest path from a vertex to all other vertices of a weighted graph.
It is similar to Dijkstra’s algorithm but it can work with graphs in which edges can have negative weights.
Why would one ever have edges with negative weights in real life?
Negative weight edges might seem useless at first but they can explain a lot of phenomena like cashflow, the heat released/absorbed in a chemical reaction, etc.
For instance, if there are different ways to reach from one chemical A to another chemical B, each method will have sub-reactions involving both heat dissipation and absorption.
If we want to find the set of reactions where minimum energy is required, then we will need to be able to factor in the heat absorption as negative weights and heat dissipation as positive weights.
Algorithm
Following are the detailed steps.
Input: Graph and a source vertex src
Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then shortest distances are not calculated, negative weight cycle is reported.
1) This step initializes distances from the source to all vertices as infinite and distance to the source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.
2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of vertices in given graph.
…..a) Do following for each edge u-v
………………If dist[v] > dist[u] + weight of edge uv, then update dist[v]
………………….dist[v] = dist[u] + weight of edge uv
3) This step reports if there is a negative weight cycle in graph. Do following for each edge u-v
……If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”
The idea of step 3 is, step 2 guarantees the shortest distances if the graph doesn’t contain a negative weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative weight cycle
Description of the algorithm
Let us assume that the graph contains no negative weight cycle. The case of presence of a negative weight cycle will be discussed below in a separate section.
We will create an array of distances d[0…n−1], which after execution of the algorithm will contain the answer to the problem. In the beginning we fill it as follows: d[v]=0, and all other elements d[] equal to infinity ∞.
The algorithm consists of several phases. Each phase scans through all edges of the graph, and the algorithm tries to produce relaxation along each edge (a,b) having weight cc. Relaxation along the edges is an attempt to improve the value d[b] using value d[a]+c. In fact, it means that we are trying to improve the answer for this vertex using edge (a,b)(a,b) and current response for vertex a.
It is claimed that n−1 phases of the algorithm are sufficient to correctly calculate the lengths of all shortest paths in the graph (again, we believe that the cycles of negative weight do not exist). For unreachable vertices the distance d[] will remain equal to infinity ∞.
Implementation
Unlike many other graph algorithms, for Bellman-Ford algorithm, it is more convenient to represent the graph using a single list of all edges (instead of nn lists of edges – edges from each vertex). We start the implementation with a structure edgeedge for representing the edges. The input to the algorithm are numbers nn, mm, list ee of edges and the starting vertex vv. All the vertices are numbered 00 to n−1n−1.
The simplest implementation
The constant INFINF denotes the number “infinity” — it should be selected in such a way that it is greater than all possible path lengths.
struct edge
{
int a, b, cost;
};
int n, m, v;
vector<edge> e;
const int INF = 1000000000;
void solve()
{
vector<int> d (n, INF);
d[v] = 0;
for (int i=0; i<n-1; ++i)
for (int j=0; j<m; ++j)
if (d[e[j].a] < INF)
d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);
// display d, for example, on the screen
}
The check if (d[e[j].a] < INF)
is needed only if the graph contains negative weight edges: no such verification would result in relaxation from the vertices to which paths have not yet found, and incorrect distance, of the type ∞−1∞−1, ∞−2∞−2 etc. would appear.
// Bellman Ford Algorithm in C
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 99999
//struct for the edges of the graph
struct Edge {
int u; //start vertex of the edge
int v; //end vertex of the edge
int w; //weight of the edge (u,v)
};
//Graph - it consists of edges
struct Graph {
int V; //total number of vertices in the graph
int E; //total number of edges in the graph
struct Edge *edge; //array of edges
};
void bellmanford(struct Graph *g, int source);
void display(int arr[], int size);
int main(void) {
//create graph
struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));
g->V = 4; //total vertices
g->E = 5; //total edges
//array of edges for graph
g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));
//------- adding the edges of the graph
/*
edge(u, v)
where u = start vertex of the edge (u,v)
v = end vertex of the edge (u,v)
w is the weight of the edge (u,v)
*/
//edge 0 --> 1
g->edge[0].u = 0;
g->edge[0].v = 1;
g->edge[0].w = 5;
//edge 0 --> 2
g->edge[1].u = 0;
g->edge[1].v = 2;
g->edge[1].w = 4;
//edge 1 --> 3
g->edge[2].u = 1;
g->edge[2].v = 3;
g->edge[2].w = 3;
//edge 2 --> 1
g->edge[3].u = 2;
g->edge[3].v = 1;
g->edge[3].w = 6;
//edge 3 --> 2
g->edge[4].u = 3;
g->edge[4].v = 2;
g->edge[4].w = 2;
bellmanford(g, 0); //0 is the source vertex
return 0;
}
void bellmanford(struct Graph *g, int source) {
//variables
int i, j, u, v, w;
//total vertex in the graph g
int tV = g->V;
//total edge in the graph g
int tE = g->E;
//distance array
//size equal to the number of vertices of the graph g
int d[tV];
//predecessor array
//size equal to the number of vertices of the graph g
int p[tV];
//step 1: fill the distance array and predecessor array
for (i = 0; i < tV; i++) {
d[i] = INFINITY;
p[i] = 0;
}
//mark the source vertex
d[source] = 0;
//step 2: relax edges |V| - 1 times
for (i = 1; i <= tV - 1; i++) {
for (j = 0; j < tE; j++) {
//get the edge data
u = g->edge[j].u;
v = g->edge[j].v;
w = g->edge[j].w;
if (d[u] != INFINITY && d[v] > d[u] + w) {
d[v] = d[u] + w;
p[v] = u;
}
}
}
//step 3: detect negative cycle
//if value changes then we have a negative cycle in the graph
//and we cannot find the shortest distances
for (i = 0; i < tE; i++) {
u = g->edge[i].u;
v = g->edge[i].v;
w = g->edge[i].w;
if (d[u] != INFINITY && d[v] > d[u] + w) {
printf("Negative weight cycle detected!\n");
return;
}
}
//No negative weight cycle found!
//print the distance and predecessor array
printf("Distance array: ");
display(d, tV);
printf("Predecessor array: ");
display(p, tV);
}
void display(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
Bellman Ford’s Complexity
Time Complexity
Best Case Complexity | O(E) |
Average Case Complexity | O(VE) |
Worst Case Complexity | O(VE) |
Space Complexity
And, the space complexity is O(V)
.
Bellman Ford’s Algorithm Applications
- For calculating shortest paths in routing algorithms
- For finding the shortest path