It depends on the implementation of the relaxation function. For example, the algorithm described in the wikipedia uses strictly a less-than
comparison: if alt < dist[v]
so in this case (and all the implementations I've seen) the shortest path from A
to D
is A -> B -> D
.
Why? Because (S
= settled nodes and Q
= queue of nodes, a pair of distance, parent):
- Start relaxing
A
, so you get the S = {A:0}
and Q = {B:3,A C:5,A D:9,A}
- From
Q
select B
and relax it. You get S = {A:0 B:3,A}
and Q = {C:(5,A) D:7,B E:10,B}
- From
Q
select C
and relax it. You get S = {A:0 B:3,A C:5,A}
and Q = {D:7,B E:10,B}
.
- From
Q
select D
and you can finish the algorithm.
Note that in step 3, you don't need to change the parent of D because the new path is not better than the current path. If the relaxation algorithm uses a less-than-or-equal
comparison, then the result will be different.