Consider the directed network $(D,w)$ with

$V(D)=\{a,b,c,d,e\},$

$A(D)=\{ab,ac,ae,bd,cd,ce,ea,eb\},$

and $w$:$A(D)R$ with

$w(ab)=2,w(ac)=2,w(ae)=1,w(bd)=2,$

$w(cd)=1,w(ce)=-3,w(ea)=1,w(eb)=1.$

$($a$)$ Give the strongly connected components of $D.$

$($b$)$ Use the Bellman$-$Ford algorithm to find a shortest directed $a-d-$path in $(D,w).$

Show your working, and give the path and its length.

$($c$)$ Does there exist a shortest directed $a-d-$walk in $(D,w)$ that is not a directed

path? Justify your answer.

Now consider an arbitrary directed network $(D,w)$ such that $w(e)0$ for all einA$(D)$

Let $u,$vinV$(D).$

$($d$)$ Give an efficient algorithm that decides whether $(D,w)$ contains a unique shortest

directed $u-v-$path. Briefly explain why the algorithm is correct and efficient.