Problem 6 A Run Dijkstra’s algorithm on the weighted graph below, using vertex s

Question

Problem 6

A

Run Dijkstra’s 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 Dijkstra’s has finished running, what are the distances from the source associated with each node?

S = 0

T =

U =

V =

W =

X =

Y =

Step #

Nodes in Queue (before extraction)

Node extracted

Nodes visited (after extraction)

Explanation / Answer

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

S = 0

T =4

U =3

V =7

W =1

X =3

Y =5

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects