Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Matt N. Jan 16 '11 at 14:40
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.