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 graph 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 graph using point 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 graph if the true Euclidean distances are replaced by the squares of the Euclidean distances (as they are above). Draw a graph that is a minimal counterexample, i.e., a weighted graph with the fewest number of vertices and edges for which the shortest path is different if we use the true Euclidean distances instead of the squares.