Lecture 29

The class began with USAT surveys.
I went over Dijktsra's shortest path algorithm today.
I gave an informal argument for why the algorithm works.
A naive implementation of the algorithm yields a O(|V|²) algorithm.
This happens to be the best we can do when the graph is dense, that is, the number of edges is O(|V|²).
However, when the graph is sparse we can do better. I will elaborate next time we meet which will be on Wednesday March 30.

Posted: Wed - March 23, 2005 at 01:45 PM

getBlogName(); > getCategoryName("C930228579"); >

Lecture 29

> >