The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w : E \u2192 R, the Bellman-Ford algorithm returns a Boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights. The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v \u2208 V until it achieves the actual shortest-path weight \u03b4(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.<\/p>\n
To understand this algorithm, we must know about the storing technique of graph.<\/p>\n
The Algorithm<\/strong> The basic idea is simple: Step 2: Take every edge and try to relax it:<\/p>\n Relaxing <\/strong> an edge means checking to see if the path to the node the edge is pointing to can\u2019t be shortened, and if so, doing it. For example Click here<\/a> <\/p>\n Here is the condensed form of the algorithm : for (i = 0; i < n; ++i) d[s] = 0;<\/p>\n for (i = 0; i < n – 1; ++i) ***the structure is 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?<\/p>\n 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. <\/p>\n Here is an real life example of bellman-Ford example . UVA 558<\/a><\/p>\n [code] typedef struct { int n; \/* the number of nodes *\/ #define INFINITY 1000000<\/p>\n void printDist() { for (i = 0; i < n; ++i) \tprintf("nn"); void bellman_ford(int s){ for (i = 0; i < n; ++i) \td[s] = 0;<\/p>\n for (i = 0; i < n-1; ++i) \/\/\/\/these 3 lines for the 558\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ if(f==1) }<\/p>\n int main() { scanf("%d",&kase); scanf("%d %d",&n,&e); for(i=0;i<e;i++){ [\/code]<\/p>\n
\nThe 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.<\/p>\n
\nStep 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:<\/p>\n
\nNow, we apply the previous step n \u2013 1 times, where n is the number of nodes in the graph. <\/p>\n
\n[code]
\nvoid bellman_ford(int s) {
\n int i, j;<\/p>\n
\n d[i] = INFINITY;<\/p>\n
\n for (j = 0; j < e; ++j)
\n if (d[edges[j].u] + edges[j].w < d[edges[j].v])
\n d[edges[j].v] = d[edges[j].u] + edges[j].w;
\n}
\n[\/code]<\/p>\n
\n[code]
\ntypedef struct{
\nint u,v,w;
\n}Edge;
\nEdge edges[1000];
\n[\/code]<\/p>\n
\n\/\/warmholes 558
\n#include <stdio.h><\/p>\n
\n\tint u, v, w;
\n} Edge;<\/p>\n
\nint e; \/* the number of edges *\/
\nEdge edges[2500]; \/* large enough for n <= 2^5=32 *\/
\nint d[1500]; \/* d[i] is the minimum distance from node s to node i *\/<\/p>\n
\n\tint i;
\n\tprintf("Distances:n");
\nfor (i = 0; i < n; ++i)
\n\t\tprintf("to %dt", i );
\n\tprintf("n");<\/p>\n
\n\t\tprintf("%dt", d[i]);<\/p>\n
\n}<\/p>\n
\n\tint i, j;<\/p>\n
\n\t\td[i] = INFINITY;<\/p>\n
\n\tfor (j = 0; j <e; ++j){
\n\t\tif (d[edges[j].u] + edges[j].w < d[edges[j].v])
\n\t\t\td[edges[j].v] = d[edges[j].u] + edges[j].w;
\n}<\/p>\n
\nint f=0;
\n for (int j = 0; j < e; j++)
\n if (d[edges[j].v] > d[edges[j].u] + edges[j].w) {
\n f=1;break;
\n }<\/p>\n
\nprintf("possiblen");
\nelse
\nprintf("not possiblen");<\/p>\n
\n\tint i,p,j,k,c,l,m,kase;
\n\tint w;<\/p>\n
\nfor(c=0;c<kase;c++){<\/p>\n
\np=0;<\/p>\n
\n scanf("%d %d %d",&j,&k,&l);
\n edges[i].u=j;
\n edges[i].v=k;
\n edges[i].w=l;
\n}
\nbellman_ford(0);
\n\/\/printDist();
\n}
\n\treturn 0;
\n}<\/p>\n