What is Dijkstra’s Algorithm? Here's How to Implement It with Example? - Simplilearn.com

TLDR: Dijkstra's algorithm finds the shortest path from one node to every other node in a weighted graph. It works by always picking the closest unvisited node and updating the distances to its neighbors from there. It requires non-negative edge weights and runs in O((V + E) log V) time with an adjacency list and a binary heap. Dijkstra’s algorithm is a shortest-path algorithm that finds the minimum distance from a starting node to every other node in a weighted graph. The algorithm works only when all edge weights are non-negative. It is widely used in routing systems, navigation software, and network optimization problems. Prerequisites: Terms You Must Know Before understanding what is Dijkstra’s algorithm, it is important to learn a few basic graph concepts. These terms appear in almost every shortest-path problem. Term Meaning Vertex (Node) A point in the graph representing an object or location. For example, a city in a road network. Edge A connection between two vertices. In a road network, this would represent a road between cities. Weight A numeric value assigned to an edge. It can represent distance, cost, time, or bandwidth. Adjacency List A data structure used to represent graphs. Each vertex stores a list of its connected neighbours and their edge weights. In most real applications, graphs are large and sparse. Because of that, adjacency lists are usually preferred over adjacency matrices. They store only the existing edges, significantly reducing memory usage. Understanding these four ideas makes the Dijkstra algorithm's logic much easier to follow. The Core Idea: Greedy Choice and Relaxation Dijkstra’s algorithm is based on a greedy algorithm strategy. At each step, it selects the vertex with the smallest tentative distance from the source and finalises that distance as the shortest. Once a vertex is chosen, its distance will never change again. The algorithm maintains a distance array that stores the shortest known distance from the source node to every other node. Initially, the distance to the source is 0, while all other nodes are set to infinity. The algorithm improves these distances through a process called edge relaxation. The Relaxation Rule For an edge from vertex u to vertex v with weight w, the relaxation rule is: if dist[u] + w < dist[v]:     dist[v] = dist[u] + w This rule checks whether the path through vertex u yields a shorter route to vertex v; if so, the algorithm updates the distance. The algorithm repeatedly performs relaxation while exploring nodes in increasing distance order. Because it always expands the nearest node, the greedy choice ensures correctness when edge weights are nonnegative. Dijkstra’s algorithm Step-by-Step The following numbered steps describe the standard version of Dijkstra’s algorithm using a priority queue. Step 1: Initialize Distances Create a distance array. Distance of the source node = 0 Distance of every other node = infinity Step 2: Create a Priority Queue Insert the source node into a min-priority queue. The queue always returns the node with the smallest distance. Step 3: Extract the Closest Node Remove the node with the smallest distance from the queue. This node becomes the current vertex. Step 4: Relax All Outgoing Edges For every neighbour v connected to the current vertex u, apply the relaxation rule: if dist[u] + weight(u,v) < dist[v]: dist[v] = dist[u] + weight(u,v) If the distance improves, update the priority queue. Step 5: Mark the Node as Visited Once all neighbours are processed, mark the node as finalized. Its shortest distance from the source is now known. Step 6: Repeat Continue extracting nodes and relaxing edges until the priority queue becomes empty. At the end of the algorithm, the distance array contains the shortest-path distances from the source to every vertex in the graph. This procedure ensures that nodes are explored in increasing order of distance, which guarantees correct results for graphs with non-negative edge weights. Worked Dijkstra Example With Distance Table To better understand what is Dijkstra's algorithm, let us use a simple graph example. Assume we have five vertices: A, B, C, D, E Edges and weights: A → B = 4 A → C = 1 C → B = 2 B → E = 4 C → D = 4 D → E = 4 The goal is to find the shortest path from A to all other nodes. Step 1: Initialization Node Distance Parent A 0 - B ∞ - C ∞ - D ∞ - E ∞ - Step 2: Visit Node A Neighbours of A: B with weight 4 C with weight 1 Relax edges: dist[B] = 4 dist[C] = 1 Node Distance Parent A 0 - B 4 A C 1 A D ∞ - E ∞ - Step 3: Visit Node C Node C has the smallest distance (1). Neighbors: B with weight 2 D with weight 4 Relaxation: dist[B] = min(4, 1 + 2) = 3 dist[D] = 5 Node Distance Parent A 0 - B 3 C C 1 A D 5 C E ∞ - Step 4: Visit Node B Neighbors: E with weight 4 Relaxation: dist[E] = 3 + 4 = 7 Node Distance Parent A 0 - B 3 C C 1 A D 5 C E 7 B Step 5: Visit Node D Neighbor: E with weight 4 Relaxation: dist[E] = min(7, 5 + 4) = 7 No change. Final Distance Table Node Shortest Distance Parent A 0 - B 3 C C 1 A D 5 C E 7 B Reconstructing the Shortest Path To rebuild the shortest path from A to E, follow the parent pointers. E → B → C → A Reverse the sequence: A → C → B → E Shortest distance = 7 Did you know? Even after all these years, Dijkstra’s algorithm is still one of the most widely taught graph algorithms in computer science. Why? Because, it combines mathematical elegance with real-world usefulness, powering everything from routing systems to navigation tools while remaining a classroom favorite. (Source: Wikipedia) Implementation in Python (Priority Queue) Before jumping into the code, it helps to understand what Dijkstra's algorithm is and what the Python implementation is trying to do. Dijkstra’s algorithm needs a way to repeatedly pick the node with the smallest current distance. In Python, this is usually done with the heapq module, which implements a min-heap. In a min-heap, the smallest element is always available at index 0, and heappop() removes that smallest element first. That makes it a natural fit for Dijkstra’s algorithm, since it always processes the closest unvisited node first. The graph is usually stored as an adjacency list. In Python, that often means a dictionary where each node points to a list of (neighbour, weight) pairs. Along with the graph, the code maintains two more dictionaries: Distances, which stores the shortest known distance from the source to each node Parent stores the previous node in the shortest path so that the full route can be rebuilt later When a shorter route is found, the code updates both dictionaries and pushes the new distance into the heap. import heapq def dijkstra(graph, start): # Set every node's distance to infinity at the beginning distances = {node: float('inf') for node in graph} # Parent map helps rebuild the shortest path later parent = {node: None for node in graph} # Distance from source to itself is always 0 distances[start] = 0 # Priority queue stores (distance, node) pq = [(0, start)] while pq: current_distance, current_node = heapq.heappop(pq) # Skip outdated entries in the heap if current_distance > distances[current_node]: continue # Check all neighbors of the current node for neighbor, weight in graph[current_node]: new_distance = current_distance + weight # Relaxation step if new_distance < distances[neighbor]: distances[neighbor] = new_distance parent[neighbor] = current_node heapq.heappush(pq, (new_distance, neighbor)) return distances, parent //Example Input Graph graph = { 'A': [('B', 4), ('C', 1)], 'B': [('E', 4)], 'C': [('B', 2), ('D', 4)], 'D': [('E', 4)], 'E': [] } Running the Function distances, parent = dijkstra(graph, 'A') print(distances) print(parent) Expected Output {'A': 0, 'B': 3, 'C': 1, 'D': 5, 'E': 7} {'A': None, 'B': 'C', 'C': 'A', 'D': 'C', 'E': 'B'} This output shows two things clearly. First, the distances dictionary gives the shortest distance from A to every other node. Second, the parent dictionary shows how each node was reached on the shortest path. One small but important detail is the check: if current_distance > distances[current_node]: continue This is used because Python’s heapq does not support directly decreasing a key. Instead of updating an existing heap entry, the algorithm pushes a new one. If a later, larger distance comes out, it is ignored. This keeps the implementation simple while still using the heap efficiently. The Python documentation notes that heapq is a heap queue implementation and that heappop() returns the smallest item, which is exactly the behavior Dijkstra’s algorithm needs. Reconstructing the Shortest Path in Python To rebuild the path, follow the parent pointers backward. def get_path(parent, target): path = [] while target is not None: path.append(target) target = parent[target] path.reverse() return path //Example get_path(parent, 'E') Output: ['A', 'C', 'B', 'E'] This approach works because the algorithm records the previous node used to reach each vertex during relaxation. Complexity and Tradeoffs When learning what is Dijkstra's algorithm, it is also important to understand how its performance depends on the data structure used for the priority queue. Time Complexity With a binary heap priority queue, the time complexity is: O((V + E) log V) Where: V = number of vertices E = number of edges Each vertex is inserted into the priority queue, and each edge may cause a relaxation update. Heap operations require logarithmic time. Also Read: Time and Space Complexity Space Complexity The space requirement is typically: O(V + E) Memory is needed to store: the graph structure the distance array the parent array the priority queue Tradeoffs Advantages Efficient for sparse graphs Widely used in routing and mapping systems Works well with adjacency lists Limitations Cannot handle negative edge weights Requires additional memory for priority queues Different implementations also change performance: Implementation Time Complexity Adjacency matrix O(V²) Binary heap + adjacency list O((V + E) log V) Fibonacci heap O(E + V log V) The heap-based version is the most commonly used in practical systems. When Not to Use Dijkstra’s Algorithm Although Dijkstra’s algorithm is powerful, it is not suitable for every graph problem. 1. Graphs With Negative Edge Weights If the graph contains edges with negative weights, the algorithm may produce incorrect results. This happens because the greedy assumption that the current shortest node is final no longer holds. In such cases, the Bellman-Ford algorithm is used instead because it can handle negative edges safely.  2. Unweighted Graphs or Equal Weights If every edge has the same weight, running Dijkstra’s algorithm is unnecessary. A simpler algorithm, Breadth-First Search (BFS), can find the shortest path more efficiently. BFS explores nodes level by level and naturally produces the shortest paths in unweighted graphs. 3. Extremely Large Graphs For very large graphs used in mapping or navigation systems, specialized algorithms may perform better. Examples include: A* search Bidirectional Dijkstra Contraction hierarchies These algorithms reduce the search space and improve performance for large road networks. Key Takeaways Dijkstra’s algorithm finds the shortest path from one source node to all other nodes in a weighted graph by always selecting the nearest unvisited node and updating neighbor distances It works only with non-negative edge weights because its greedy approach assumes the shortest known distance to a selected node will not change later The algorithm relies on edge relaxation, a process that checks whether a newly discovered path to a neighbor is shorter and updates the distance if needed A priority queue makes Dijkstra’s algorithm efficient by always returning the node with the smallest current distance for the next step Learn 30+ in-demand cybersecurity skills and tools, including Ethical Hacking, System Penetration Testing, AI-Powered Threat Detection, Network Packet Analysis, and Network Security, with our Cybersecurity Expert Masters Program. FAQs 1. How does Dijkstra’s algorithm find the shortest path? Dijkstra’s algorithm repeatedly selects the unvisited node with the smallest known distance from the source, then updates the distances of its neighbors. This process continues until the shortest paths to all reachable nodes are found. 2. Why does Dijkstra require non-negative edge weights? Dijkstra assumes that once a node gets the smallest distance, that value is final. Negative edge weights can later yield a shorter path, breaking this assumption and leading the algorithm to return incorrect results. 3. What is “edge relaxation” in Dijkstra’s algorithm? Edge relaxation means checking whether traversing the current node yields a shorter path to a neighboring node. If it does, the algorithm updates the neighbor’s distance to this new, smaller value. 4. How do you choose the next node in Dijkstra? Choose the unvisited node with the smallest tentative distance from the source. In efficient implementations, this is usually done using a min-priority queue or binary heap. 5. What is the difference between Dijkstra and BFS? BFS finds shortest paths in unweighted graphs or graphs with equal edge weights. Dijkstra works for weighted graphs with non-negative weights by choosing the path with the lowest total cost, not just the fewest edges.