Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009, recorded: November 2005, views: 105397
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)
Slides
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.
Description
"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:
mit6046jf05_demaine_lec18_01.pdf (286.5 KB)
Download mit6046jf05_demaine_lec18_01.m4v (Video - generic video source 159.8 MB)
Download mit6046jf05_demaine_lec18_01.rm (Video - generic video source 123.6 MB)
Download mit6046jf05_demaine_lec18_01.flv (Video 213.3 MB)
Download mit6046jf05_demaine_lec18_01_320x240_h264.mp4 (Video 229.9 MB)
Download mit6046jf05_demaine_lec18_01.wmv (Video 681.1 MB)
Download mit6046jf05_demaine_lec18_01.mp3 (Audio lecture 17.8 MB)
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:
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.
Thanks alot! Very usefull
very informative and provides good stuff..
very usefull! thanks so much
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
Cheers
John
John,
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.
this is very useful thanku sir
fantastic and useful
thank you very much
Super helpful just before the test!!!
Самые надежные места для изготовления дубликатов номеров в Москве, посмотреть.
Нюансы изготовления дубликатов
Write your own review or comment: