Problem 6

A

Run Dijkstras algorithm on the weighted graph below, using vertex s as the source. For each step of the algorithm, list the nodes currently in the queue, the node extracted at that step, and the nodes visited (a.k.a relaxed) at that step. Assume that, once a node has been extracted, it is not visited via the adjacency list of another node.

Step #	Nodes in Queue (before extraction)	Node extracted	Nodes visited (after extraction)

B

After Dijkstras has finished running, what are the distances from the source associated with each node?

S = 0

T =

U =

V =

W =

X =

Y =

5 4 9 2 2