Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search

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: 64634
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.


"We're going to talk about shortest paths, and we're going to talk about shortest paths for three lectures. So, this is a trilogy. Today will be Shortest Paths One. I've been watching far too many versions of Star Wars this weekend. I saw the musical yesterday, matinee. That was an MIT musical. That was fun, of all three movies in about four hours. That was a bit long and then I saw the one-man show on Friday. One-man Star Wars: the original three movies in one hour. That was the opposite of too long. Both were fun. So I get my trilogy fix. All episodes, first we're going to start with The New Hope, and we're going to talk about the shortest paths problem and solve one particular problem of it, a very interesting version...

See Also:

Download slides icon Download slides: mit6046jf05_demaine_lec17_01.pdf (450.8 KB)

Download Video - generic video source Download mit6046jf05_demaine_lec17_01.m4v (Video - generic video source 174.5 MB)

Download Video - generic video source Download mit6046jf05_demaine_lec17_01.rm (Video - generic video source 135.2 MB)

Download Video Download mit6046jf05_demaine_lec17_01.flv (Video 235.1 MB)

Download Video Download mit6046jf05_demaine_lec17_01_320x240_h264.mp4 (Video 251.3 MB)

Download Video Download mit6046jf05_demaine_lec17_01.wmv (Video 746.4 MB)

Download audio transcript Download mit6046jf05_demaine_lec17_01.mp3 (Audio lecture 19.5 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 jan@janth.dk, December 8, 2009 at 8:05 p.m.:

This class has been a great help for me.
I am studying computer science at noea.dk.

Jan Penuel.

Comment2 Sarah, January 8, 2010 at 5:01 p.m.:

Thank you for posting these extensive lectures on shortest paths. They have been brilliant resources for my Computer Science degree at Warwick University, England.

Comment3 abhishek sharma, December 22, 2010 at 12:36 p.m.:

excellent uploads....
i get to understand more and thoroughly.......

Comment4 3bdennour, December 26, 2010 at 9:12 p.m.:

Thank you
May ALLAH reward the Teacher

Comment5 Chandrasekaran, October 11, 2011 at 4:15 a.m.:

Thanks. It helps me to teach better.

Write your own review or comment:

make sure you have javascript enabled or clear this field: