NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Shortest Paths

1. Consider the following weighted directed graph.

weighted digraph

Run Dijkstra's single source shortest path algorithm on the above digraph using A as the source. Give the order in which the vertices are first dequeued from the priority queue. 


0    1    2    3    4    5    6    7    8
-----------------------------------------
A
Also give the distance of the shortest path from A to each vertex v and the last edge on the shortest path to v. 


v        dist[v]       pred[v]
--       -------       -------

A          0            null

B

C

D

E

F

G

H

I