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

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett