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

author:Erik Demaine, Center for Future Civic Media
published: Feb. 10, 2009,   recorded: November 2005,   views: 3712
You might be experiencing some problems with Your Video player.

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.

Description

"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)

Launch Windows Media PlayerLaunch in a standalone WM Player

WMedia PlayerSwitch to Windows Media Player

View slides View slides

Download Flash video Download mit6046jf05_demaine_lec17_01.flv (Flash video 235.1 MB)

Download mp4 video Download mit6046jf05_demaine_lec17_01.m4v (mp4 video 174.5 MB)

Download Real media video Download mit6046jf05_demaine_lec17_01.rm (Real media video 135.2 MB)

Download Windows Media video Download mit6046jf05_demaine_lec17_01.wmv (Windows Media video 746.4 MB)

Download audio transcript Download mit6046jf05_demaine_lec17_01.mp3 (Audio transcript 19.5 MB)


Help icon Streaming Video Help

WebLink icon Windows Media Player Firefox Plugin - Download

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.

Write your own review or comment:

make sure you have javascript enabled or clear this field: