# Dijkstra's Algorithm - two solutions possible?

I did a homework question, which was choosing the shortest path to the other points from a point using Dijkstra's Algorithm.

I ended up with the following, whilst an online applet resulted in something else (upper graph is my try, lower one is the applet's one):

(The vertices in the second image have different names, but I tried to use the same shape of the graph.)

So, instead of B-D I did E-D. For D, the routes B-D and B-E-D are of equal length, so I was wondering whether both are indeed correct.

Thanks.

-

## 1 Answer

The solution to the shortest path problem is not unique.

Imagine you have a 2-node graph, let's call the nodes A and B. You have, say, 10 edges between them, all of equal weight w. Then the shortest path from A to B is any one of these 10 edges, so the solution is not unique. In particular, it depends on the order in which you traverse the nodes in each iteration.

-
I see, thanks. So am I right in thinking that both solutions are correct? –  pimvdb Jan 16 '11 at 13:09
If you get the same length as the other solution probably yes. –  Rudy the Reindeer Jan 16 '11 at 14:40
Note that this answer is true also for simple graphs; consider $K_n$ with $w(e) = c$, $c \in \mathbb{R}$. –  Raphael Jan 16 '11 at 15:36