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>
\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

The basic idea is simple:
\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

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.
\nNow, we apply the previous step n \u2013 1 times, where n is the number of nodes in the graph. <\/p>\n

For example Click here<\/a> <\/p>\n

Here is the condensed form of the algorithm :
\n[code]
\nvoid bellman_ford(int s) {
\n int i, j;<\/p>\n

for (i = 0; i < n; ++i)
\n d[i] = INFINITY;<\/p>\n

d[s] = 0;<\/p>\n

for (i = 0; i < n – 1; ++i)
\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

***the structure is
\n[code]
\ntypedef struct{
\nint u,v,w;
\n}Edge;
\nEdge edges[1000];
\n[\/code]<\/p>\n

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]
\n\/\/warmholes 558
\n#include <stdio.h><\/p>\n

typedef struct {
\n\tint u, v, w;
\n} Edge;<\/p>\n

int n; \/* the number of nodes *\/
\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

#define INFINITY 1000000<\/p>\n

void printDist() {
\n\tint i;
\n\tprintf("Distances:n");
\nfor (i = 0; i < n; ++i)
\n\t\tprintf("to %dt", i );
\n\tprintf("n");<\/p>\n

for (i = 0; i < n; ++i)
\n\t\tprintf("%dt", d[i]);<\/p>\n

\tprintf("nn");
\n}<\/p>\n

void bellman_ford(int s){
\n\tint i, j;<\/p>\n

for (i = 0; i < n; ++i)
\n\t\td[i] = INFINITY;<\/p>\n

\td[s] = 0;<\/p>\n

for (i = 0; i < n-1; ++i)
\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

\/\/\/\/these 3 lines for the 558\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\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

if(f==1)
\nprintf("possiblen");
\nelse
\nprintf("not possiblen");<\/p>\n

}<\/p>\n

int main() {
\n\tint i,p,j,k,c,l,m,kase;
\n\tint w;<\/p>\n

scanf("%d",&kase);
\nfor(c=0;c<kase;c++){<\/p>\n

scanf("%d %d",&n,&e);
\np=0;<\/p>\n

for(i=0;i<e;i++){
\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

[\/code]<\/p>\n

References:
\n“Introduction to algorithms ” by Coreman
\nhttp:\/\/compprog.wordpress.com\/2007\/11\/29\/one-source-shortest-path-the-bellman-ford-algorithm\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

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 … <\/p>\n

Continue reading “Bellman-Ford Algorithm”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0},"categories":[15],"tags":[],"_links":{"self":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts\/97"}],"collection":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=97"}],"version-history":[{"count":0,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts\/97\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=97"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=97"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=97"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}