Study Guide  Tucker: Applied Combinatorics  §4.1 Shortest Paths Dr. Lee Eimers

Introduction:  A spanning tree is a subgraph that is a tree and visits every vertex of the original graph. In this section we will learn different ways to build and traverse spanning trees and some of their uses, and some of the associated concepts that are very important in current research.

1.  Be able to construct the modified graph for Dijkstra's Algorithm to find the minimal distance from a given vertex to any other vertex in the graph.  Know how to apply the result to find the actual path as well.  Dijkstra's Algorithm is O(n log n).

2.  Know how to do Floyd's Algorithm to find the minimal distance between any pair of vertices.  Floyd's Algorithm is O(n^3).

3. From 1 and 2 above, we find that applying Dijkstra's algorithm n times to find the distances for any pair of vertices would take n applications of the algorithm and would be  O((n^2) log n), which is still more efficient than Floyd's Algorithm for large n.