NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Shortest Paths

1. Consider the following weighted directed graph.
   

   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
   
   

2. Also give the distance of the shortest path from C to each vertex v (except A) and the last edge on the shortest path to v.

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