Dijkstra’s Algorithm with Python Implementation
- Samul Black
- Aug 19, 2024
- 4 min read
Updated: Aug 6
Dijkstra’s Algorithm is a classic and fundamental algorithm in computer science used for finding the shortest path from a starting node to all other nodes in a weighted graph. Named after its creator, Edsger W. Dijkstra, the algorithm is widely used in various applications such as network routing, geographical mapping, and optimization problems. In this blog, we’ll explore the core concepts of Dijkstra’s Algorithm, its implementation in Python, and some practical applications.

What is Dijkstra’s Algorithm?
Dijkstra’s Algorithm is a foundational graph traversal algorithm used to compute the shortest path from a single source node to all other nodes in a weighted graph—provided all edge weights are non-negative. It is widely used in routing and navigation systems, such as GPS mapping software, network packet routing, and AI pathfinding in games.
Originally proposed by Dutch computer scientist Edsger W. Dijkstra in 1956, this algorithm laid the groundwork for many modern optimization techniques in graph theory and has become an essential tool in computer science and operations research.
Why Use Dijkstra’s Algorithm?
Dijkstra's Algorithm is especially useful in real-world applications where finding the shortest or most cost-effective route is essential. Examples include:
GPS Navigation: Calculating the shortest driving distance between two locations.
Internet Routing: Finding the least-cost path for data packets across a network.
Project Planning: Determining the quickest path through a series of dependent tasks.
Video Games and Robotics: Guiding characters or agents through obstacle-laden environments.
Key Concepts in Dijkstra’s Algorithm
To fully understand Dijkstra’s Algorithm, it’s important to grasp the following core concepts:
Shortest Path: The smallest total weight (or cost) from the source node to a target node, considering all valid routes.
Priority Queue (Min-Heap): A data structure that efficiently selects the node with the current shortest known distance for processing. This helps the algorithm focus on the most promising paths first.
Distance Vector (Distance Array): An array or mapping that keeps track of the shortest known distance from the source node to every other node. Initially, all distances are set to infinity, except for the source node, which is set to zero.
Visited Set: A collection of nodes that have already been fully processed and won’t be revisited, preventing unnecessary computation.
Dijkstra’s Algorithm: Step-by-Step Breakdown
Here’s a high-level breakdown of how Dijkstra’s Algorithm works:
1. Initialization
Assign a tentative distance value to every node:
0 for the source node.
∞ (infinity) for all other nodes.
Create an empty priority queue (min-heap) and insert the source node with a priority of 0. Initialize a set or boolean array to keep track of visited nodes.
2. Processing Nodes
While the priority queue is not empty:
Extract the node u with the smallest distance from the priority queue.
If u has already been visited, skip it.
For each unvisited neighbor v of node u:
Calculate the tentative distance:distance[u] + weight(u, v)
If this tentative distance is less than the currently recorded distance for v, update it.
Insert or update node v in the priority queue with the new distance.
Mark node u as visited.
3. Termination
The algorithm continues until:
All reachable nodes have been visited, or
The priority queue becomes empty.
At this point, the distance vector contains the shortest path distances from the source node to all other nodes in the graph.
Python Implementation for Dijkstra’s Algorithm
Let’s implement Dijkstra’s Algorithm in Python using a priority queue for efficient retrieval of the node with the smallest distance.
import heapq
def dijkstra(graph, start):
# Initialize distances with infinity
distances = {node: float('inf') for node in graph}
distances[start] = 0 # Distance to source is 0
# Priority queue to select the node with the smallest distance
priority_queue = [(0, start)] # (distance, node)
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# Skip if we found a better path already
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
# If a shorter path to neighbor is found
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# Example graph (undirected and weighted)
graph = {
'A': [('B', 2), ('C', 5)],
'B': [('A', 2), ('C', 6), ('D', 1)],
'C': [('A', 5), ('B', 6), ('D', 3), ('E', 8)],
'D': [('B', 1), ('C', 3), ('E', 4)],
'E': [('C', 8), ('D', 4)]
}
start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(f"Shortest distances from node '{start_node}':")
for node, distance in shortest_distances.items():
print(f" - {node}: {distance}")
Output:
Shortest distances from node 'A':
- A: 0
- B: 2
- C: 5
- D: 3
- E: 7
This implementation of Dijkstra’s Algorithm uses a priority queue (min-heap) to always process the next closest node. The distances dictionary keeps track of the current shortest distance from the start node to every other node. At each step, the algorithm extracts the node with the smallest known distance, checks all its neighbors, and updates their distances if a shorter path is found. If a neighbor's distance is updated, it is pushed into the priority queue so it can be processed later. The process continues until all reachable nodes have been processed. The final result is a dictionary mapping each node to its shortest distance from the source.
Conclusion
Dijkstra’s Algorithm is a fundamental and versatile tool for solving shortest path problems in graphs with non-negative edge weights. Its combination of efficiency, simplicity, and wide applicability makes it a go-to solution in numerous domains—from GPS navigation and internet routing to game development and logistics. By leveraging a greedy approach and efficient data structures like priority queues, it ensures optimal results with minimal computational overhead.
With the Python implementation provided, you're equipped to begin applying Dijkstra’s Algorithm to your own graph-based problems—be it in educational projects, business applications, or real-world systems
As you deepen your understanding, consider exploring variations like A* Search for heuristic-based pathfinding or Bellman-Ford for handling negative weights. Dijkstra’s Algorithm is not just a classic—it’s a critical building block in the toolkit of every programmer, data scientist, and engineer.