ECE Ph.D. Qualifying Exam

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).

Back to QE CE question 1, August 2015

Back to ECE Qualifying Exams (QE) page

Alumni Liaison

Ph.D. on Applied Mathematics in Aug 2007. Involved on applications of image super-resolution to electron microscopy

Francisco Blanco-Silva