Dijkstra’s algorithm

Dijkstra’s algorithm finds the shortest path from a single source node to every other node in a weighted graph, as long as no edge carries a negative weight. Edsger W. Dijkstra devised it in 1956 and published it in 1959, and it remains the standard solution to the single-source shortest-path problem.

The algorithm is greedy, which means it always takes the shortest option in front of it and never goes back to reconsider. It assigns every node a tentative distance, zero for the source and infinity for the rest, then repeatedly settles the unvisited node with the smallest tentative distance, fixing that distance as final.

Settling that node relaxes each of its edges, lowering a neighbor’s distance whenever the path through the settled node proves shorter than the neighbor’s current estimate.

The visualization below traces this process step by step: it settles the nearest unsettled node from the priority queue and relaxes its edges, lowering neighbors’ tentative distances until the shortest-path tree is complete.

Because a settled node’s distance is treated as final, the method cannot handle negative edge weights, which could otherwise expose a cheaper route to a node already locked in.

Performance depends on the data structure used to find the next node to settle. The cost is usually stated in Big O notation over V nodes and E edges:

• Linear scan: Checking every tentative distance on each step gives O(V^2) time, which suits dense graphs.
• Binary heap: A min-heap used as a priority queue brings a sparse graph down to O((V + E) log V), and Python’s heapq module supplies one.
• Fibonacci heap: A more advanced priority queue lowers the theoretical bound to O(E + V log V).

Dijkstra’s algorithm computes the routes in link-state protocols such as OSPF, and it drives the shortest-path search in mapping and GPS software. Breadth-first search is its special case for unweighted graphs, A* adds a heuristic to steer the search toward a single target, and the Bellman-Ford algorithm trades some speed to handle negative edge weights.

Related Resources

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources:

• The Python heapq Module: Using Heaps and Priority Queues (Tutorial)
• Python Stacks, Queues, and Priority Queues in Practice (Tutorial)
• Sorting Algorithms in Python (Tutorial)
• How to Do a Binary Search in Python (Tutorial)
• Mazes in Python: Build, Visualize, Store, and Solve (Course)
• Python Stacks, Queues, and Priority Queues in Practice (Quiz)
• Introduction to Sorting Algorithms in Python (Course)
• Creating a Binary Search in Python (Course)