Name:

$11$

$15.(4$ points$)$ Suppose we run the Dijkstra algorithm on the following graph starting from s$.$ List the vertices in the order they are dequeued from the queue.

$16.(6$ points$)$

$($a$)(2$ points$)$ Explain the "optimality of subpaths" lemma.

$($b$)(2$ points$)$ Explain why $(s,v)(s,u)+w(u,v)$ for any edge $(u,v).$ Make your solution concise.

$($c$)(2$ points$)$ Suppose all edges have weight $1$ in the input directed graph $G=(V,E).$ Wha is the fastest way to compute shortest path from $s$ to $t,$ where $s,$tinV $?$ What is th time? running time?