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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .