1
$\begingroup$

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): graphs

(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 Answers 1

4

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.

  • 1
    Note that this answer is true also for simple graphs; consider $K_n$ with $w(e) = c$, $c \in \mathbb{R}$.2011-01-16