Problem $3.$ Give an example of a simple, undirected, weighted graph such that a breadth$-$first traversal outputs

a search$-$tree that is not a single source shortest path tree. $($That is$,$ BFS is not sufficiently powerful to solve

the shortest$-$path problem on weighted graphs. This motivates Dijkstra's algorithm, which will be discussed in

the near future.$)$ Your answer must:

$($a$)$ Draw the graph $G=(V,E,w)$ by specifying $V$ and $E,$ clearly labeling the edge weights. $[$Note: We have

provided TikZ code below if you wish to use $IA{T}_{E}x$ to draw the graph. Alternatively, you may hand$-$draw $G$

and embed it as an image below, provided that $($i$)$ your drawing is legible and $($ii$)$ we do not have to rotate

our screens to grade your work.$]$

$($b$)$ Specify a spanning tree $T(V,E_T)$ that is returned by BFS$,$ but is not a single$-$source shortest path tree.

$[$Note: You may again hand$-$draw this tree. If you wish, you may clearly mark the edges of $T$ on your

drawing of $G.$ Please make it easy on the graders to identify the edges of $T.]$

$($c$)$ Specify a valid single$-$source shortest path tree $T^{\text{'}}=(V,E_{T^{\text{'}}}).[$Note: You may again hand$-$draw this tree.

If you wish, you may clearly mark the edges of $T$ on your drawing of $G.$ Please make it easy on the graders

to identify the edges of $T.]$

$($d$)$ Include a clear explanation of why the search$-$tree output by breadth$-$first search is not a valid single$-$source

shortest path tree of $G.$

Answer.