Lecture 32
Today we saw a template for single source
shortest path algorithms. Common to all of the algorithms is an iterative step
that moves vertices one by one from an "Unseen" ,
U,
part to the the "seen" or "Tree",
T,
part. The differences are in how the decisions are made for moving a vertex from
U
to
T.
We saw a very nice and clever
implementation of Dijkstra's algorithm for positive weighted digraphs. This
algorithm uses a priority queue to help decide which vertex to move from
U
to
T.
The second algorithm we saw is
for undirected graphs where the edges are unweighted, and the implicit cost of
every edge is 1. Here a breadth first traversal of the graph is used to decide
which vertex to move from
U
to
T.
.
On Friday I will review
questions for quiz #3.
Posted: Wed - March 30, 2005 at 01:53 PM