Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints

author: Erik Demaine, Center for Future Civic Media, Massachusetts Institute of Technology, MIT
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009,   recorded: November 2005,   views: 105385
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


"Good morning, everyone. Glad you are all here bright and early. I'm counting the days till the TA's outnumber the students. They'll show up. We return to a familiar story. This is part two, the Empire Strikes Back. So last time, our adversary, the graph, came to us with a problem. We have a source, and we had a directed graph, and we had weights on the edges, and they were all nonnegative. And there was happiness. And we triumphed over the Empire by designing Dijkstra's algorithm, and very efficiently finding single source shortest paths, shortest path weight from s to every other vertex...

See Also:

Download slides icon Download slides: mit6046jf05_demaine_lec18_01.pdf (286.5 KB)

Download Video - generic video source Download mit6046jf05_demaine_lec18_01.m4v (Video - generic video source 159.8 MB)

Download Video - generic video source Download mit6046jf05_demaine_lec18_01.rm (Video - generic video source 123.6 MB)

Download Video Download mit6046jf05_demaine_lec18_01.flv (Video 213.3 MB)

Download Video Download mit6046jf05_demaine_lec18_01_320x240_h264.mp4 (Video 229.9 MB)

Download Video Download mit6046jf05_demaine_lec18_01.wmv (Video 681.1 MB)

Download audio transcript Download mit6046jf05_demaine_lec18_01.mp3 (Audio lecture 17.8 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 mohamad, December 15, 2009 at 2:10 a.m.:

thanks.. your lessons really do help.. just found this site today... i'll probe into it to see find other useful stuff.. thanks a lot.

Comment2 tomy dragon, December 17, 2009 at 9:32 a.m.:

Thanks alot! Very usefull

Comment3 ARCHANA, January 21, 2011 at 6:14 p.m.:

very informative and provides good stuff..

Comment4 carlos, September 12, 2011 at 4:20 a.m.:

very usefull! thanks so much

Comment5 John Oke, October 2, 2011 at 2:17 p.m.:

Lecture 18, Bellman Ford Algorithm
I enjoyed the layman's version of Bellman Ford algorithm. Having created your table , how do you find the shortest path from the table. I shall be very grateful.
Secondly when in real life do we find negative weight either on its own or with positive weights
Thirdly may we please have an example of a negative weight cycle and where it exists in real life


Comment6 Lena, October 10, 2011 at 6:12 a.m.:


Imagine you have a series of roads (edges) between towns (vertices). Each road has a fuel cost associated with how much fuel you burn to travel across it. But some roads have refuelling stations, giving them a negative fuel cost.

For the negative weight cycle, I'd say there's some example representing buying and selling items, where on your way to buying something you can buy and sell things in an infinite loop, gaining more and more money (negative cost). But I'm sure there are more practical examples too.

Comment7 samar choudhary, December 13, 2011 at 6:20 p.m.:

this is very useful thanku sir

Comment8 مهندسة مصرية مسلمة, June 2, 2013 at 9:50 a.m.:

fantastic and useful
thank you very much

Write your own review or comment:

make sure you have javascript enabled or clear this field: