Posted by: atri | November 2, 2010

Lect 26: Shortest Path Problem

In today’s lecture, we studied Dijkstra’s shortest path algorithm and proved its correctness. The slides have been uploaded.

For more information on Dijkstra, check out his wikipedia page. For more on his “EWD” manuscripts, check out the UT Austin page.

Next lecture, we will quickly wrap up the run time analysis of Dijkstra’s algorithm and then move on to the Minimum Spanning Tree problem (Sec 4.5 in the book).

Below are links to the student blog posts for the lecture:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: