CIS126 – Search Tree

Weighted Graph 

      Most often when we need to compute the shortest path from a topological map the distances between vertices vary greatly.  So the shortest path is not necessarily the one with the fewest edges to traverse.  Below we have the same graph as before, but with weights (shown in blue) assigned to the edges.

      As we go to build a search tree we can no longer prune the tree simply because we have previously encountered a vertex.  We must take into account the cost of reaching the vertex by each of the routes.  We do this by using this rubric: If a vertex we produce is already on the tree, we compare the total cost of each of the two paths to that vertex.  And we discard (prune) the vertex with the greater cost.  Moreover, if the vertex to be pruned is at the root of a subtree already in the graph, we prune the entire subtree.  This power point file shows how such a tree would be built.  Again we seek the shortest route from vertex 7 to vertex 12. 

Exercises:

1. Build a search tree to find the shortest path from vertex 1 to vertex 12.

2. Build a search tree to find the shortest path from vertex 3 to vertex 6.

3. What is the Big-O category of this algorithm?