Computer Engineering(CE)
Question 1: Algorithms
August 2015
Solution 1
It turns out that we need only four vertices to construct the proscribed example. Consider the graph consisting of the four vertices $ A,B,C $, and $ D $. We will take $ A $ to be the source vertex, and the graph will have the following edges/weights:
$ \bullet\,A\rightarrow B = 1 $
$ \bullet\,A\rightarrow C = 0 $
$ \bullet\,A\rightarrow D = 2 $
$ \bullet\,B\rightarrow C = 1 $
$ \bullet\,D\rightarrow B = -5 $
It is clear that the shortest path from $ A $ to $ C $ has a cost of -2, but Dijkstra's algorithm will operate on the graph as follows:
$ \bullet $ We set $ d(A,A) $ = 0 and all other distances $ d(\cdot,\cdot) $ to $ \infty $.
$ \bullet $ Following edges from $ A $, we set $ d(A,B)=1,\, d(A,C)=0 $, and $ d(A,D)=2 $.
$ \bullet $ We attempt to follow edges away from $ C $, but there are none so we move on.
$ \bullet $ We attempt to follow the edge from $ B $ to $ C $, but $ d(A,B)+d(B,C)>d(A,C) $, so we move on.
$ \bullet $ Following the edge from $ D $ to $ B $, we set $ d(A,B)=d(A,D)+d(B,D)=-3 $.
$ \bullet $ We have visited all vertices, so we are done. We conclude that the shortest path distances from $ A $ are $ d(A,B)=-3,\, d(A,C)=0 $, and $ d(A,D)=2 $.
Clearly we have not found the correct set of shortest path distances using Dijkstra's algorithm, since there is a discrepancy between the true $ d(A,C) $ (-2) and the one that we have found (0).
