NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Shortest Paths

1. Consider the following weighted directed graph.
   

   Give the distance of the shortest path from C to each vertex v (except A and C) and the last edge on the shortest path to v. Put your answers for the edgeTo column in the form A -> C

   
   v        distTo[v]       edgeTo[v]
   --       ---------       ---------
   A        infinity          null
   
   B
   
   C            0             null
   
   D
   
   E
   
   F
   
   G
   
   H
   
   I
   

2. Run Dijkstra's single source shortest path algorithm on the above digraph using C as the source. Give the order in which the vertices are removed from the priority queue. Note that A is not reachable from C, so it is never added (and thus never removed) from the priority queue.

   
   0    1    2    3    4    5    6    7
   ------------------------------------
   C