Warmup with Dijkstra. $(25$ points$)$

Let G $=($V;E$)$ be a weighted directed graph. For the rest of this problem, assume that

s; t $2$ V and that there exists a directed path from s to t$.$

For the rest of this problem, refer to the implementation of Dijkstra's algorithm given by

the pseudocode below.

$2$

dijkstra$\_$st$\_$path$($G$,$ s$,$ t$)$:

for all v in V$,$ set d$[$v$]=$ Infinity

for all v in V$,$ set p$[$v$]=$ None

$//$ we will use p to reconstruct the shortest s$-$t path at the end

d$[$s$]=0$

F $=$ V

D $=[]$

while F isn't empty:

x $=$ vertex v in F such that d$[$v$]$ is minimized

for y in x$.$outgoing$\_$neighbors:

d$[$y$]=$ min$($ d$[$y$],$ d$[$x$]+$ weight$($x$,$y$))$

if d$[$y$]$ was changed in the previous line, set p$[$y$]=$ x

F$.$remove$($x$)$

D$.$add$($x$)$

$//$ use p to reconstruct the shortest s$-$t path

path $=[$t$]$

current $=$ t

while current $!=$ s:

current $=$ p$[$current$]$

add current to the front of the path

return path, d$[$t$]$

The variable p maintains the $\backslash$parents$"$ of the vertices in the shortest s$-$t path, so it can

be reconstructed at the end.

Step through dijkstra st path$($G; s; t$)$ on the graph G shown below. Complete the table

below to show what the arrays d and p are at each step of the algorithm, and indicate

what path is returned and what its cost is$.$

s u

v

t

$3$

$1$

$2$

G $4$

$[$We are expecting the table below $$lled out, as well as the $$nal shortest path

and its cost. No further justi$$cation is required.$]$

$3$

d$[$s$]$ d$[$u$]$ d$[$v$]$ d$[$t$]$ p$[$s$]$ p$[$u$]$ p$[$v$]$ p$[$t$]$

When entering the $$rst while loop

for the $$rst time, the state is:

$0111$ None None None None

Immediately after the $$rst ele$-$

ment of D is added, the state is:

$0311$ None s None None

Immediately after the second ele$-$

ment of D is added, the state is:

Immediately after the third ele$-$

ment of D is added, the state is:

Immediately after the fourth ele$-$

ment of D is added, the state is:

$3.$