In this article, I describe the Bellman-Ford algorithm for finding the one-source shortest paths in a graph, give an informal proof and provide the source code in C for a simple implementation.
To understand this you should know what a graph is, and how to store one in memory. If in doubt check this and this.
Another solution to this problem is Dijkstra’s algorithm.
The Problem
Given the following graph, calculate the length of the shortest path from node 1 to node 2.
It’s obvious that there’s a direct route of length 6, but take a look at path: 1 -> 4 -> 3 -> 2. The length of the path is 7 – 3 – 2 = 2, which is less than 6. BTW, you don’t need negative edge weights to get such a situation, but they do clarify the problem.
This also suggests a property of shortest path algorithms: to find the shortest path form x to y, you need to know, beforehand, the shortest paths to y‘s neighbours. For this, you need to know the paths to y‘s neighbours’ neighbours… In the end, you must calculate the shortest path to the connected component of the graph in which x and y are found.
That said, you usually calculate the shortest path to all nodes and then pick the ones you’re intrested in.
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:
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:
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. In the above graph, by checking the edge 1 -> 2 of length 6, you find that the length of the shortest path to node 1 plus the length of the edge 1 -> 2 is less then infinity. So, you replace infinity in node 2 with 6. The same can be said for edge 1 -> 4 of length 7. It’s also worth noting that, practically, you can’t relax the edges whose start has the shortest path of length infinity to it.
Now, you apply the previous step n – 1 times, where n is the number of nodes in the graph. In this example, you have to apply it 4 times (that’s 3 more times).
That’s it, here’s the algorithm in a condensed form:
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;
}
Here, d[i] is the shortest path to node i, e is the number of edges and edges[i] is the i-th edge.
It may not be obvious why this works, but take a look at what is certain after each step. After the first step, any path made up of at most 2 nodes will be optimal. After the step 2, any path made up of at most 3 nodes will be optimal… After the (n – 1)-th step, any path made up of at most n nodes will be optimal.
The Programme
The following programme just puts the bellman_ford function into context. It runs in O(VE) time, so for the example graph it will do something on the lines of 5 * 9 = 45 relaxations. Keep in mind that this algorithm works quite well on graphs with few edges, but is very slow for dense graphs (graphs with almost n2 edges). For graphs with lots of edges, you’re better off with Dijkstra’s algorithm.
Here’s the source code in C (bellmanford.c):
#include <stdio.h>
typedef struct {
int u, v, w;
} Edge;
int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[1024]; /* large enough for n <= 2^5=32 */
int d[32]; /* d[i] is the minimum distance from node s to node i */
#define INFINITY 10000
void printDist() {
int i;
printf("Distances:\n");
for (i = 0; i < n; ++i)
printf("to %d\t", i + 1);
printf("\n");
for (i = 0; i < n; ++i)
printf("%d\t", d[i]);
printf("\n\n");
}
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;
}
int main(int argc, char *argv[]) {
int i, j;
int w;
FILE *fin = fopen("dist.txt", "r");
fscanf(fin, "%d", &n);
e = 0;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j) {
fscanf(fin, "%d", &w);
if (w != 0) {
edges[e].u = i;
edges[e].v = j;
edges[e].w = w;
++e;
}
}
fclose(fin);
/* printDist(); */
bellman_ford(0);
printDist();
return 0;
}
And here’s the input file used in the example (dist.txt):
5
0 6 0 7 0
0 0 5 8 -4
0 -2 0 0 0
0 0 -3 9 0
2 0 7 0 0
That’s an adjacency matrix.
That’s it. Have fun. Always open to comments.
2008-02-08 at 12:58
Thanks a lot for explanation.I have a doubt it detects negative edge cycles.What about the shortest will that be found.Will that include that negative edge also.Will that negative edge be skipped while calculating the shortest path.
2009-12-08 at 1:23
You can use this algorithm to detect negative edge cycles by going 1 step further (for a total of n loops). If a change occurs between the (n-1)th and nth loop, there is a negative edge cycle.
Unfortunately, leaving this vertex out in any shortest path decisions is a much more difficult thing to do.
To put it simply: The Bellman-Ford algorithm can detect negative loops, but it can’t work around them.
2011-02-22 at 10:53
To be specific, any negative weigthed cycle reachable from source only not each!!
2008-02-29 at 15:27
thank you :)
2008-03-12 at 6:01
what’s the difference between Dijkstra and Bellman-Ford? i think it’s similar. would u like to differ them by their each steps?
2009-12-08 at 1:31
Basically the Dijkstra’s method marks each node as ‘visited’ once it relaxes all edges from that node, and will not try to relax any edges leading back to that node after that point. It then chooses the node with the lowest value from the initial node, as the next ‘current’ node.
Since at each step i out of n nodes, you are relaxing at most n-i edges, (instead of n-1 like Bellman-Ford’s), this algorithm completes much quicker than Bellman-Ford’s, and scales better with a larger number of nodes. The main drawback is that it will not work with negative edge weights.
2012-02-12 at 7:33
dijkstra algorithm can be applied to only positive weights, but bellman ford algorithm is applied for both positive and negative weights….
2008-03-18 at 18:17
I think there is a simple difference btween Dijkstra and Bellman-Ford….like – Bellman-Ford work with negetive weight cycles and relax many time….but Dijkstra not work with negetive cycle and relax only one time…
2010-03-18 at 16:38
Dijkstra cannot work with negative weights at all. If you try it, result will not be shortest path. In JUNG implementation of dijkstra it throws exception if some edge has negative weight.
2011-07-06 at 20:07
No algorithm works with negative weight cycle.
Every algorithm fails in case of negative weight cycle.
Bellman ford works with negative weight edges whereas Dijkstra doesn’t.
2008-05-07 at 21:28
Thanks for the explanation. By the way, can you show me how to find the shortest path in sudoku problem?
2008-05-27 at 22:17
can you tell us how to print also the path of the shortest distance.thanks a lot.
2008-09-09 at 5:53
Yeees, how to print also the path of the shortest distance? thanks in advance.
2008-10-21 at 16:12
Very good explanations. Much better than my textbook (and my professor). Thanks
2008-11-24 at 22:21
thanx a lot for explaining, you explained it better than my teacher :)
2009-02-28 at 22:56
This tutorial is excellent.It has helped me a lot.More tutorial should be published.
2009-03-01 at 12:21
thanx… lot of help to the assignment, the dijkstras and bellman ford does arises some complexities but they do differ from negative weights…. thanx again…………. keep it up
2009-03-23 at 21:57
Bellman-Ford’s algorithm returns TRUE if the graph contains no negative weight cycles that are reachable from the source.
So the above source needs some additions to check the above requirement.
For pseudo code you may check this link
Click to access bellman-ford-screen.pdf
2009-03-25 at 15:55
Thanks a lot!! :)
2009-03-26 at 17:06
is there any way to print out the actual path? i.e. node 1 to 3 to 5
2011-02-22 at 11:02
yes but in reverse. reminding u’ve set parent to the node.. use that..
or u can use recursion to print in sequence
2009-03-27 at 13:30
Ford the best car :)
2009-03-29 at 4:10
Hi … Does anyone have an example of a real situation where negative weights are used?? Thanks !
2009-03-31 at 17:09
If i have to laydown the telephone network around the 50 houses around my apartment …Which shortest path method should i use to get it work for me …please explane..
2009-04-02 at 17:17
Ford is a good car :)
2009-04-19 at 16:07
Thanks a lot.
2009-05-06 at 0:37
Can the source ever become negative?
2011-02-03 at 14:26
If the source were to ever become negative, then it would be due to a negative weight cycle.
2009-05-18 at 19:11
Thanks alot..
This is simple and helpful :)
2009-07-01 at 15:47
Great article! However, I was interested in knowing how we could modify your algorithm to find the Kth shortest path from a source to a node,ie, for K=2,how to find the second shortest path..?
2009-09-07 at 17:08
how i find shortest distance when source node 2,3,4,5.
2009-07-25 at 12:38
thanks alot…
2009-10-21 at 4:12
Very lucid explanation! Thanks for your efforts!
2009-11-11 at 10:05
thanks a lot…
2009-11-16 at 1:20
awesome tuto…it really helps in understanding this algo.Thanks for your efforts!
2009-11-17 at 23:59
**** you nerds
2009-11-22 at 18:26
Excelente este manual…..
Me sirvio para entender mi clase
Gracias
2009-12-05 at 7:53
thanks a lot…but is it detect negative cycle??
2009-12-08 at 23:12
good explation
2009-12-12 at 7:33
can you please tell me how to print Path in Bellman algorithm ..like the way its done in Dijsktra.
Please provide the code sample if you have..Thanks in advance.
2009-12-21 at 22:30
Thank you very much, excellent explanation (Y) really thank you.
I have only one question kindly answer it: what u,v,w represent in this code? it seems to be a silly question.
Thanks in advance
2010-01-02 at 15:21
Hi,
thank you very much.
I think you adjecency matrix has a little mistake: the nine ought to be one spot to the right?
To detect negative circles:
Just let the first for loop go one further, then make an if statement in the existing if statement like if (n == n-1) … an then stop the function and print “negative circle”
2010-01-10 at 16:18
thank you so much , but the result of this program , is only a matrice , how can’i found the shortest path from onr node to a destination , for example : from 1 to 5.
thank you
2010-03-27 at 15:48
Thanks for your clear explanation. I have a question that how can I improve this code to find K-th shortest paths.
thank you
2010-04-01 at 9:31
Cool Dude !!!
2010-04-22 at 7:08
wow… who are you buddy ??? This article is incredibly good, clear and simple. Thank you very much for your article. I’ll must recommend my pals to read your article.
2010-05-06 at 19:03
thaks very much
2010-06-05 at 5:22
bagus!!
2010-07-23 at 3:53
Thanks! The best explanation of Bellman-Ford I have encountered.
2010-08-12 at 19:52
Thanks a lot…nice tutorial..
2010-09-01 at 17:11
[…] algorithm ( https://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/ […]
2010-10-19 at 16:02
Thankx a lot……..
2010-12-03 at 15:21
So bellman-ford detects if there’s a negative cycle and tops there?
Doesn’t it find the shortest route by skipping the negative cycle also?
2010-12-03 at 15:22
So bellman-ford detects if there’s a negative cycle and tops there?
Doesn’t it find the shortest route by skipping the negative cycle also?
liviu.c.doro@gmail.com
2010-12-18 at 5:27
has anyone executed this algorithm by taking the source instead of 0?
2011-02-03 at 15:24
Can someone please tell me how the algorithm publishes the shortest path?
2011-03-13 at 18:27
hey i have a question for u all? Can i use Dijsktra algoritm instead of Bellmans for megative weighted graphs, if I add a number for every arc in graph that makes every arc non-negative?
2011-04-17 at 7:27
thanks
2011-05-15 at 0:35
[…] For example Click here […]
2011-05-28 at 20:56
In belmann_ford()
for (j = 0; j < e; ++j)
if (d[edges[j].u] + edges[j].w<d[edges[j].v])
printf("Negativeee Circle\n\n");
hm?
otherwise(){thanks:)}
2011-08-05 at 8:37
can u any1 tell me what’s the meaning of negative significance(negative weight cycle) in bellman algoritm
2011-08-22 at 1:19
It was helpful. Thank u so much:-)
2011-10-02 at 9:19
So what is thew shortst path and how do you find/work it out
Thanking you in advance
Indiana
2011-10-08 at 18:41
Can You plz provide the matlab code for Bellman ford algorithm.
Sonal
2011-10-11 at 13:19
lalala pila
2011-10-15 at 20:57
hola quiero descargar( aquí está el archivo de entrada utilizado en el ejemplo ( DIST.TXT ): ) pero no lo se como soy nuevo usuario, porfavor si pueden me lo embian mi cuenta es abnerself…, o abner.systems@hotmail.com
2011-11-05 at 1:56
taman negara pahang…
[…]One Source Shortest Path: The Bellman-Ford Algorithm « Computer programming[…]…
2011-11-13 at 0:23
Very well done. The description of “relaxing an edge” appears in Wikipedia, but they don’t give any explanation of what that means. Thanks.
2011-11-21 at 19:30
I still don’t get this. In the first loop iteration of the outer loop, let’s say by ur example, u first modify edge 1->2 and edge 1->4, what’s the problem in modifying the edge 2->3, 2->5, 4->3, 4->5, since we have d[2] and d[4] now.
2011-11-25 at 8:12
Thanks!!! =D
2011-11-26 at 16:03
Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the
maximum over all pairs of vertices u, v V of the minimum number of edges in a shortest
path from u to v. (Here, the shortest path is by weight, not the number of edges.) Suggest a
simple change to the Bellman-Ford algorithm that allows it to terminate in m + 1 passes.plz solve this…
2011-12-04 at 6:13
Is there any Matlab code for the Bellman-ford algorithm. I will appreciate if someone can point me to one please. Thanks.
2011-12-04 at 6:14
Is there any Matlab code for the Bellman-ford algorithm. Thanks.
2011-12-15 at 4:17
Hello I wonder if it is possible to print the nodes where he found the best way would be and how to do this?
2012-01-01 at 15:29
thamks alot This really helped me….
2012-01-09 at 21:05
maternity fashion…
[…]One Source Shortest Path: The Bellman-Ford Algorithm « Computer programming[…]…
2012-01-11 at 2:02
Samir…
[…]One Source Shortest Path: The Bellman-Ford Algorithm « Computer programming[…]…
2012-03-03 at 16:41
its not clear
2012-03-06 at 6:25
can u explain the problem in stepwise..
2012-04-22 at 13:41
i am not be able to open dist.txt file in Bellman–Ford algorithm example plz help me
thanks ;
2012-04-22 at 18:50
Reblogged this on ameenos2000.
2012-04-26 at 8:04
Simple. Concise. I liked it.
2012-04-26 at 16:18
Thanks ! For an awesome explanation! was struggling for it….
but I needed a java program for this….thanks anyways!
2012-05-14 at 1:01
nice
2012-05-16 at 18:05
thanks a lotttttttttttttttttt
2012-06-18 at 15:47
when there is positive weights than dijikstras will be applied and for negative weights bellmanford is applied
2012-06-25 at 15:23
Hi there! I am trying to do some kind of programming exercise here on Bellman-Ford algorithm, I’m good with algorithms but I don’t have much experience with program languages, not even c. I understood a lot from the way you built your program but unfortunately I can’t open the text you were using to import your data, it takes me to a page where it says that should be logged in (I am) and a member of your blog (following is not enough? :( ). I’d really appreciate it if you could help me see that text. Thank you very much.
2012-07-31 at 17:40
Can anyone tell me the application of Bellman ford algo and where these negative edge are used?
2012-08-12 at 20:35
how can i print the shortest path?
2012-09-25 at 14:25
it’s gud…………….
2012-10-07 at 17:21
hi, i want to ask, how about the implementation on java?
is it has big difference with C?
thank you :)
2012-10-31 at 11:30
no comments…………….
2012-11-11 at 20:12
panditAJI
2012-11-19 at 20:21
Thanks a million!
2012-12-17 at 3:31
Thank you so much :D
2012-12-18 at 9:30
Am getting segmentation fault when I execute this program.
2013-02-16 at 10:53
ultimate….
thank u..
2013-04-03 at 1:11
Hey There. I found your blog using msn. This is a very neatly written article. I will be sure to bookmark it and come back to read extra of your helpful info. Thank you for the post. I will definitely return.
2013-04-04 at 14:54
can you explain about the input file dist.txt
2013-05-28 at 13:50
where are the value in the vertices stored???
2013-06-26 at 12:40
Thanks !!!! I searched various sites for this explanation.. This one was the best.. It make me understand the algorithm properly !!
2013-07-17 at 18:18
It seems to me finding the shortest path with Floyd Warshal and Bellman-Ford is very similar, the algorithm differs, but the pattern seems the same to me. What’s the difference really I can’t seem to find it, when going through the graph?
2014-01-27 at 20:25
thank’s . i can’t open the file dist.txt plz help me
2014-03-12 at 20:06
Good post. I learn something new and challenging on blogs
I stumbleupon on a daily basis. It will always be interesting to read through articles
from other writers and use a little something from other web sites.
2014-09-24 at 3:05
Hungry Shark Evolution Hack Triche Gratuit
One Source Shortest Path: The Bellman-Ford Algorithm | Computer programming
2014-09-24 at 4:53
Castle Clash Triche
One Source Shortest Path: The Bellman-Ford Algorithm | Computer programming
2014-09-30 at 15:31
I’m not that much of a internet reader to be honest but your sites really nice, keep it up!
I’ll go ahead and bookmark your website to come back later.
Many thanks
2014-10-01 at 13:56
Injustice Hack
One Source Shortest Path: The Bellman-Ford Algorithm | Computer programming
2014-10-07 at 11:14
It’s great that you are getting thoughts from this article as
well as from our argument made at this place.
2014-10-07 at 12:15
It’s awesome to pay a visit this web page and reading the
views of all colleagues regarding this post, while I am
also eager of getting know-how.
2014-11-11 at 2:13
[…] with Implementation 2 […]
2014-11-20 at 9:09
Inputs: A sequence A = (a1, . . . , an) of n real numbers, and two real
numbers p and q.
Output: The number of elements of A that are more than or equal to
p and less than or equal to q.
Give a recursive algorithm, NumberInRange(A, p, q, i) that solves
this problem. e algorithm, NumberInRange(A, p, q, i) that solves
this problem. Note that the parameter i is needed to record
which part of the sequence A is being considered for a given
recursive call. So NumberInRange(A, p, q, i) returns the number
of values within the range that are in the subsequence (a1, . . . , ai)
2015-07-27 at 16:53
[…] Bellman Ford algorithm : Tutorial, Implementation, Tutorial, Implementation, Problem, Problem […]
2015-09-04 at 5:38
[…] Ford algorithm : tutorial with implementation, tutorial with implementation, problem, […]
2015-10-01 at 0:00
[…] As a Cisco engineer you really do not have to understand how DUAL or BellmanFord operate internally. It really is just an abstract operation with a well defined result. However, if you are like me, you want to understand what’s underneath the hood. One of these days I’m going to write a simple implementation of either BellmanFord or DUAL in Perl or Python. In the meantime, here is a interesing blog on BellmanFord https://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/ […]
2015-12-07 at 19:04
I agree with what you say and I am very much like you in that respect. However, there is another reason for which you might want to know what is happening under the hood except for our natural curiosity.
That is, if you want to improvise on top of existing knowledge and produce some new one. Knowing how algorithms work will allow your brain to combine and recombine until you get something new and hopefully better. It is like learning music rather than just a series of songs.
2015-11-05 at 11:21
Thank you!
2015-12-26 at 4:51
[…] The only other graph traversal algorithm I did not cover is called the Bellman-Ford algorithm which has the ability to work with negative weighted edges. Much like Dijkstra’s shortest path, it is also used to find the shortest available path on graphs that have negative edge costs. I found a good tutorial with explanation here for this: https://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/ […]
2016-05-30 at 11:47
wow,,, it has been very helpful to clear out my doubts
thank u sooo much
2017-01-10 at 16:39
i just need a matlab coding for bellman ford algorithm
2017-04-19 at 7:18
Sir tutorial is awesome just one doubt , why at after any general k step at most k-1 nodes path is optimal how we can say this without knowing future path which will get optimal in future?? Here k<=n-1 any general step
2017-05-04 at 4:49
Great blog you have here but I was curious if you knew of any forums
that cover the same topics discussed in this article?
I’d really like to be a part of online community
where I can get advice from other knowledgeable people
that share the same interest. If you have any recommendations,
please let me know. Thank you! http://worldofgame.eu/groups/7-romantic-driving-games-ideas/
2017-07-03 at 9:22
Arama motorlarında arama yaparken yazınızı buldum paylaşımlarınız dikkatimi çekti teşekkürlerimi sunarım
2018-02-10 at 17:37
Makalelerinizi ilgiyle takip ediyorum
2020-02-10 at 22:23
[…] https://compprog.wordpress.com […]