To understand this algorithm, we must know about the storing technique of graph.

The Algorithm
The Bellman-Ford algorithm is one of the classic solutions to this problem. It calculates the shortest path to all nodes in the graph from a single source.

The basic idea is simple:
Step 1: Start by considering that the shortest path to all nodes, less the source, is infinity. Mark the length of the path to the source as 0:

Step 2: Take every edge and try to relax it:

Relaxing an edge means checking to see if the path to the node the edge is pointing to can’t be shortened, and if so, doing it.
Now, we apply the previous step n – 1 times, where n is the number of nodes in the graph.

For example Click here

Here is the condensed form of the algorithm :
[code]
void bellman_ford(int s) {
int i, j;

for (i = 0; i < n; ++i)
d[i] = INFINITY;

d[s] = 0;

for (i = 0; i < n – 1; ++i)
for (j = 0; j < e; ++j)
if (d[edges[j].u] + edges[j].w < d[edges[j].v])
d[edges[j].v] = d[edges[j].u] + edges[j].w;
}
[/code]

***the structure is
[code]
typedef struct{
int u,v,w;
}Edge;
Edge edges[1000];
[/code]

It is seen that the working principle of Bellman-Ford algorithm is exactly same as another single source shortest path Dijkstra’s algorithm. Then what is the difference between them?

Yes, their working principle is same but Dijkstra’s algorithm fails if there exists any negative valued weight or negative cycle. But Bellman-Ford algorithm is capable to determine the negative cycle in the graph and finds the shortest path even with negative valued weights.

Here is an real life example of bellman-Ford example . UVA 558

[code]
//warmholes 558
#include <stdio.h>

typedef struct {
int u, v, w;
} Edge;

int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[2500]; /* large enough for n <= 2^5=32 */
int d[1500]; /* d[i] is the minimum distance from node s to node i */

#define INFINITY 1000000

void printDist() {
int i;
printf("Distances:n");
for (i = 0; i < n; ++i)
printf("to %dt", i );
printf("n");

for (i = 0; i < n; ++i)
printf("%dt", d[i]);

printf("nn");
}

void bellman_ford(int s){
int i, j;

for (i = 0; i < n; ++i)
d[i] = INFINITY;

d[s] = 0;

for (i = 0; i < n-1; ++i)
for (j = 0; j <e; ++j){
if (d[edges[j].u] + edges[j].w < d[edges[j].v])
d[edges[j].v] = d[edges[j].u] + edges[j].w;
}

////these 3 lines for the 558////////////////
int f=0;
for (int j = 0; j < e; j++)
if (d[edges[j].v] > d[edges[j].u] + edges[j].w) {
f=1;break;
}

if(f==1)
printf("possiblen");
else
printf("not possiblen");

}

int main() {
int i,p,j,k,c,l,m,kase;
int w;

scanf("%d",&kase);
for(c=0;c<kase;c++){

scanf("%d %d",&n,&e);
p=0;

for(i=0;i<e;i++){
scanf("%d %d %d",&j,&k,&l);
edges[i].u=j;
edges[i].v=k;
edges[i].w=l;
}
bellman_ford(0);
//printDist();
}
return 0;
}

[/code]

References:
“Introduction to algorithms ” by Coreman
http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/