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 edge lengths to be weights (as in the Exercises on MST), consider the weighted directed 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.