Dijkstra's algorithm: Difference between revisions

Revision as of 13:49, 13 April 2025

Revision as of 13:35, 14 April 2025

Line 19:

== Algorithm ==

[[File:Dijkstras_progress_animation.gif|thumb|Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a target node (upper right, green) in a [[Robotics|robot]] [[motion planning]] problem. Open nodes represent the "tentative" set (aka set of "unvisited" nodes). Filled nodes are the visited ones, with color representing the distance: the redder, the closer (to the start node). Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular [[wavefront]] as Dijkstra's algorithm uses a [[Consistent heuristic|heuristic]] of picking the shortest known path so far.]]

The algorithm requires a starting node, and nodecomputes ''N,''the with ashortest distance betweenfrom thethat starting node andto ''N''each other node. Dijkstra's algorithm starts with infinite distances and tries to improve them step by step:

# Create a [[Set (abstract data type)|set]] of all unvisited nodes: the unvisited set.