Dijkstra's algorithm: Difference between revisions

Revision as of 09:13, 16 December 2024

Revision as of 17:11, 16 December 2024

Line 202:

In fact, Dijkstra's explanation of the logic behind the algorithm:{{sfn|Dijkstra|1959|p=270}}

{{blockquote|'''Problem 2.''' Find the path of minimum total length between two given nodes <math>{{mvar|P</math>}} and <math>{{mvar|Q</math>}}.

We use the fact that, if <math>{{mvar|R</math>}} is a node on the minimal path from <math>{{mvar|P</math>}} to <math>{{mvar|Q</math>}}, knowledge of the latter implies the knowledge of the minimal path from <math>{{mvar|P</math>}} to <math>{{mvar|R</math>}}.}}

is a paraphrasing of [[Richard Bellman|Bellman's]] [[Bellman equation#Bellman's principle of optimality|Principle of Optimality]] in the context of the shortest path problem.