Posted by: atri | October 29, 2012

Lect 24: Dijkstra’s Algorithm

In today’s lecture started talking about the shortest path problem and then we sort of “derived” Dijkstra’s algorithm. Next lecture, we will prove the correctness of the algorithm and do its run time analysis. All this material is from Section 4.4 in the textbook.

The slides and notes have been uploaded.

Here is a link to the archived webpage of Dijkstra, where the article appear as “EWD”s. I mis-spoke a bit in class: his articles where not always hand written but they started in the 70s I think. For more information check out his Wikipedia page.

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: