Dijkstra's Algorithm

Core Concept

Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a starting node to all other reachable nodes in a weighted graph. It strictly requires non-negative edge weights to function correctly.

Execution Steps

• Initialize all node distances to infinity, except the starting node which is set to 0.
• Extract the unvisited node with the absolute lowest distance using a Priority Queue.
• Relax the edges: if a tentative path through the current node is cheaper than a neighbor's recorded distance, overwrite the neighbor's distance.
• Repeat until the Priority Queue is empty.

Visual Representation

Further Reading

For a mathematical proof and history, visit the Wikipedia page for Dijkstra's Algorithm.