NAMES:

LOGINS:

PRECEPT:

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


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


v        dist[v]       prev[v]
--       -------       -------

A

B

C

D

E

F

G

H

I