I am confused about this situation that happened to me as I was trying to solve a shortest path problem using Dijkstra's Algorithm.
'$s$' is the starting point and '$t$' is finish.
When I reach to the point where my Visited set is $S_5=\{s,d,a,e,b,h\}$, I have two options to continue from to the next Current vertex, they are both equal and from what I have been reading, when you get to a situation where you have two equal weights you choose arbitrarily. The problem is, when I choose arbitrarily here, one path is shorter than the other:
If I choose: $S_7=\{s,d,a,e,b,h,g,t\}$, then I get $l(t)=12$.
If I choose: $S_7=\{s,d,a,e,b,h,f,t\}$, then I get $l(t)=9$.
How do I know which one to choose from when I get equal weights? because it obviously affects the whole path.
Best Answer
$t$ should not be a member of your $S_7$ in any case.
Steps 6, 7, and 8 will add nodes $f$, $g$ and $j$ to to the working set, in some arbitrary order, because all are at a distance of $8$ from the starting node. So these nodes will always get added before you start considering things at larger distance.
If you add $g$ in step 6, you don't immediately proceed to connect $g$ to $t$ -- that must only happen in a later step. And since reaching $t$ through $g$ has a path length of 12, this only happens (if at all) after you have processed all nodes at a closer distance than 12 from the starting node -- in particular $f$ will also have been processed then.
Depending on whether you add $f$, $g$ or $j$ first, the first finite distance we know for $t$ might be 12 -- but we're not actually visiting $t$ (and terminating the algorithm) unless its best known distance is minimal among all unvisited nodes.
(Also, there's plainly no way to reach $t$ is distance 9, but $s-d-e-f-t$ reaches it in distance 10).