Lecture 26
Today we saw several graph algorithms. I
described two types of graph traversals, depth first, and breadth first. These
traversal algorithms have a computational complexity that is proportional to the
size of the input when they are implemented with an adjacency list. The
different traversals have different uses. We saw one immediate use of breadth
first search with respect to finding shortest paths in graphs where all edges
have the same weight.
The
singles source shortest path problem accepts a weighted connected graph together
with a distinguished vertex v0 and reports the weight of shortest
paths from v0 to all vertices in the graph. We saw two very easy
special cases. For a more general case we are in the midst of developing the so
called, Dijkstra's algorithm. The basic idea behind this algorithm is to build a
spanning tree that contains all of the requisite shortest paths. The algorithm
works on a partition of the vertex set into two subsets U (unknown, or unseen
vertices) and T (the shortest path spanning tree). Every iteration of the
algorithm moves a vertex from U to T, until the entire tree is built. I will
continue with the details of the algorithm and show that by using a heap we can
obtain an implementation that runs in O( |E| log |E|) time and O(|E|) space.
Posted: Wed - March 14, 2007 at 11:31 AM