Use Dijkstra's algorithm to find the shortest path from u to w for the following graph.

A graph with $7$ vertices and $11$ edges is shown.

One edge with weight $7$ connects vertex t and vertex u$.$

One edge with weight $3$ connects vertex t and vertex w$.$

One edge with weight $15$ connects vertex t and vertex x$.$

One edge with weight $2$ connects vertex u and vertex v$.$

One edge with weight $1$ connects vertex u and vertex x$.$

One edge with weight $8$ connects vertex u and vertex y$.$

One edge with weight $10$ connects vertex v and vertex y$.$

One edge with weight $7$ connects vertex v and vertex z$.$

One edge with weight $5$ connects vertex w and vertex x$.$

One edge with weight $2$ connects vertex x and vertex y$.$

One edge with weight $5$ connects vertex y and vertex z$.$

The table below is similar to Table $10\mathrm{.}6\mathrm{.}1.$ Fill in the missing entries to show the action of the algorithm.

Step

V$($T$)$

E$($T$)$

F

L$($t$)$

L$($u$)$

L$($v$)$

L$($w$)$

L$($x$)$

L$($y$)$

L$($z$)$

$0$

$\{$u$\}$

$$

$\{$u$\}$

$\backslash$infty $0\backslash$infty $\backslash$infty $\backslash$infty $\backslash$infty $\backslash$infty

$1$

$\{$u$\}$

$$

$\{$t$,$ v$,$ x$,$ u$\}$

$702\backslash$infty $18\backslash$infty

$2$

$\{$u$,$ x$\}$

$\{\{$u$,$ x$\}\}$

$2\backslash$infty

$3$

$\{$u$,$ x$,$ v$\}$

$4$

$5$

The table shows the lengths of the shortest paths from u to all the other vertices of the graph. In particular, it shows that the shortest path from u to w has length $.$

In Step $2,$

D$($x$)=$ u;

in Step $3,$

D$($v$)=$ ;

in Step $4,$

D$($y$)=$ ;

and in Step $5,$

D$($w$)=.$

Tracing backwards from w gives

D$($w$)=$

and

D$$

$=.$

So$,$ the shortest path is $.$