Lecture 27. 



Today we revisited the FWI all-to-all shortest path algorithm. I used the data projector to show a run of the algorithm. A PDF version of the presentation is attached below.

I then returned to the one to all shortest path problem and Dijkstra's algorithm that we started on Wednesday. I began where I left out giving the key points needed to justify the correctness of the algorithm. The algorithm was presented in two forms. One a high level version, that left the actual details some steps of the implementation vague. Using this version I demonstrated the algorithm on a small example graph. I then refined the implementation making use of a min-heap to obtain an efficient running time.

Recall that we assume that the input graph is connected. The conclusions regarding Dijkstra's algorithm drawn by the end of the lecture are:

- Using an adjacency matrix representation of the graph uses Ω(|V|2) time and space.
- A straight forward implementation uses O(|V|2) time.
- If the graph is sparse that is |E| << |V| then
- we can gain efficiencies in space by using an adjacency list representation of the graph yielding O(|E|) space complexity.
- we can gain efficiencies in time with a clever use of a heap yielding O(|E| log |E|) time complexity.
- The algorithm's correctness is limited to graphs (or directed graphs) with non-negative edge weights.

allToAllShortest.pdf 

Posted: Fri - March 16, 2007 at 11:26 AM          

©