0
$\begingroup$

I have trouble putting this into formal mathematical terms, so let's suppose that I found the shortest path from A to E as A > C > D > B > F > E with Dijkstra's algorithm. Am I correct in assuming that the shortest path from C to B would be C > D > B, and that the shortest path from D to F would be D > B > F?

$\endgroup$
3
$\begingroup$

Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we denote it as $p_{CB}$. Then we would have a path $A \rightarrow p_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A \rightarrow C \rightarrow D \rightarrow B \rightarrow F \rightarrow E$.

$\endgroup$
1
$\begingroup$

If you check what Dijkstra's algorithm does, it computes the shortest paths to all nodes from a given start node.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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