Dijkstra's algorithm - paradox

Question

I am solving next Dijkstra's algorithm.

S - start, T - final. In first step I choose $C(102)$. Next step I choose $E(187)$. Third step I choose $G(304)$ because it is less than $F(310)$. Then from $G$ I can go only to $T(426)$ Paradox is that if I go from $E$ to $F$ and then $T$ path is shorter, but I do not know that in $E$ position. How can I solve this using algorithm. Should I do backwards checks from $T$ to $F$ and $G$, or I miss anything?

Answer 1

There is no paradox, you are simply not applying the algorithm in its entirety. Just because $B$ is further away than $C$ at the first step doesn't mean that you disregard it forever.

You need to consider each and every path and keep track of the shortest way to get to every point in the graph, so that in the end, in particular you have the shortest path leading to the goal.

Example of the induction step in the algorithm: you know the shortest path to go to $B$ and also to go to $C$. Now to go to $E$

• either you go from $C$
• or you go from $B$
• (or you go from $B$ through $F$ but this will be taken care of later)

So keep the shortest of these two ways. Now you have two ways to go to $F$, from $B$ or from $E$. If the shortest path to $F$ was from $B$ you might have to update the shortest path to $E$ (eg if instead of $195$ and $123$ you had $1$ and $2$).

Answer 2

Your stated algorithm is not Dijkstra's Algorithm.

For the real Dijkstra's Algorithm, every time a vertex is processed, the neighboring vertices also have to be updated. And every time we must select a vertex, we should select the one with minimum distance processed but still active.

Your algorithm was a greedy algorithm which turns to fail in this case.