### 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.