Dijkstra's Algorithm

A classic algorithm that finds the shortest path from a start node to every other node in a graph with non-negative edge weights.

Dijkstra's algorithm was conceived by the Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, for finding the shortest single-source paths on a graph whose edge weights (traversal costs) are all non-negative. It works by tracking the currently known shortest distance to every node, repeatedly picking the not-yet-finalized node with the smallest distance, and using it to update the distances of its neighbors. It's guaranteed to find the optimal solution, and with a binary heap it runs in about O((V+E)logV), where V and E are the numbers of nodes and edges. A* is a generalization of it: A* adds an estimate of the remaining distance to the goal (a heuristic function) and prioritizes searching toward the target, so it expands fewer nodes. In robot navigation, each cell of a grid map is a node, and the value in the costmap serves as the edge weight; Nav2's default NavFn planner can be configured to expand with either Dijkstra or A*.

ExampleThree points A, B, C: A→B costs 1, B→C costs 2, and a direct A→C link costs 4. The algorithm finalizes B first (at distance 1), then uses B to update C's distance from 4 down to 3, giving A→B→C as the final shortest path.

Related

A* Search · Path Planning · Costmap · Global Planning and Local Planning · Hybrid A*

Sources

Wikipedia: Dijkstra's algorithm
Nav2 Docs: NavFn Planner（wavefront Dijkstra or A*）