NAME:

PRECEPT:

LOGIN:

COS 226 Exercises on Shortest Paths

1. Label the following points in the plane A through I, respectively: 
 (1, 3) (2, 1) (2, 6) (1, 6) (6, 6) (3, 4) (3, 6) (5, 2) (5, 7)
Taking the squares of the Euclidean distances to be weights, consider the weighted digraph defined by the edges 
A->B A->C C->G F->G B->F B->E B->H B->D D->H E->I G->I E->F E->H
Run Dijkstra's single source shortest path algorithm on the above digraph using A as the source. Give the order in which the shortest path tree edges are selected. Also draw the shortest path from A to every other vertex.

















2. Dijkstra's algorithm may not compute the shortest path in the original digraph if the true Euclidean distances are replaced by the squares of the Euclidean distances (as they are above). Draw a digraph that is a minimal counterexample, i.e., a weighted digraph with the fewest number of vertices and edges for which the shortest path is different if we use the Euclidean distances instead of their squares.