b$)$ Consider the following directed, weighted graph with negative weight edges:

i Step through Dijkstra's algorithm to calculate supposedly shortest paths from A to every other vertex. Show your steps in the table below. Cross out old values and write in new ones, from left to right within the cell, as the algorithm proceeds. List the vertices in the order which you marked them known.

$[6$ marks$]$

$\backslash$table$[[$Vertext$,$Distance,Path$],[$A$,0,$A$],[$B$,2,$A$],[$C$,7,$A$],[$D$,,],[$E$,12,],[$F$,,],[$G$,,]]$

ii Dijkstra's algorithm found the wrong path to some of the vertices. For just the vertices where the wrong path was computed, indicate both the path that was computed and the correct path.

marks$]$

iii What single edge could be removed from the above graph such that Dijkstra's algorithm will compute the correct answers for all vertices in the remaining graph.

$[2$ marks$]$