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

## Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood