$24\mathrm{.}3-7$

Let G$=($V$,$E$)$ be a weighted, directed graph with positive weight function

w:E$->\{1,2,$dots,W$\}$ for some positive integer W$,$ and assume that no two ver$-$

tices have the same shortest$-$path weights from source vertex s$.$ Now suppose that

we define an unweighted, directed graph G$^(\text{'})=($V$\backslash$cup V$^(\text{'}),$E$^(\text{'}))$ by replacing each

edge $($u$,$v$)$inE with w$($u$,$v$)$ unit$-$weight edges in series. How many vertices

does G$^(\text{'})$ have? Now suppose that we run a breadth$-$first search on G$^(\text{'}).$ Show that

Chapter $24$ Single$-$Source Shortest Paths

the order in which the breadth$-$first search of G$^(\text{'})$ colors vertices in V black is the

same as the order in which Dijkstra's algorithm extracts the vertices of V from the

priority queue when it runs on G$.$