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

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Participants2253
BellmanFord 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 subreactions 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 V1 times where V is the number of vertices in given graph.
…..a) Do following for each edge uv
………………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 uv
……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 BellmanFord 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<n1; ++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