Dijkstra's algorithm: Difference between revisions

Revision as of 02:33, 21 July 2025

Latest revision as of 18:47, 18 August 2025

(One intermediate revision by one other user not shown)

Line 49:

8

9 '''while''' ''Q'' is not empty:

10 ''u'' ← vertex in ''Q'' with minimum dist[vu]

11 Q.remove(u)

12

Line 205:

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

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

== See also ==