Consider the following directed, weighted graph of $7$ network routers labelled $A,B,C,D,E,F,G.$

a$)$ Step through Dijkstra's algorithm to calculate supposedly

cheapest path from router $C$ to every other router in the

network. Clearly cross out old values and write in new ones

as the algorithm proceeds. $(5$ marks$).$

b$)$ Dijkstra's algorithm found the wrong path to some of the

routers. For just the routers where the wrong path was

computed, indicate both the wrongly computed path and the

correct path. $(8$ marks$)$

c$)$ What single edge could be removed from the graph such

that Dijkstra's algorithm would happen to compute correct

answers for all routers in the remaining graph? Justify your

answer. $(4$ marks$)$

d$)$ What are the best$-$ and worst$-$case running times of the Bellman$-$Ford algorithm? Explain. $(8$ marks$)$