Dijkstra’s algorithm

In short: Dijkstra’s algorithm finds, in a graph with non-negative edge weights, the shortest path from a start node to all others.

In more detail: It maintains the best known distance for each node. In each step it takes the unfinished node with the smallest tentative distance and checks whether the paths to its neighbours become shorter via it (“relaxation”).

In Depth

• Data structure: With a priority queue (heap) it reaches O((V + E) log V).
• Requirement: no negative weights. For that there is Bellman-Ford.
• A*: adds an estimate of the remaining distance (heuristic) to Dijkstra and so searches more purposefully. Widespread in games and navigation.
• Uses: route planning, network routing (OSPF), game pathfinding.
• Example: nodes A–B (4), A–C (1), C–B (2): the path A→C→B (3) is shorter than A→B (4).

See also: Breadth-first and depth-first search (BFS and DFS), Greedy algorithms