A Complete Guide to Dijkstra’s Shortest Path Algorithm

When we think of finding the shortest path between two points—whether on a digital map, a network, or a graph—Dijkstra’s algorithm stands as one of the most efficient and widely used solutions. Developed by computer scientist Edsger W. Dijkstra in 1956 and published in 1959, Dijkstra’s algorithm has become a foundational concept in computer science and graph theory.

In this tutorial, we’ll explore what Dijkstra algorithm is, how it works, how to implement it programmatically, and more.

Let’s start the discussion with a brief overview of Dijkstra’s algorithm.

What is Dijkstra’s algorithm?

Dijkstra’s algorithm (or Dijkstra’s shortest path algorithm) is used to find the minimum distance from a starting node (source) to every other node in a weighted graph with non-negative edge weights.

We can think of it as a method of gradually exploring paths from the source node and continuously updating the shortest known distance to each node until the optimal solution is found. This process ensures that we always move toward the most efficient route possible.

For example, if we use Dijkstra algorithm in a road network, the nodes represent cities, and the edges represent roads with distances as weights. The algorithm helps us find the shortest driving route between two cities.

Now that we’ve got an idea of what Dijkstra’s algorithm is, let’s take a closer look at how it actually works step-by-step.

How Dijkstra algorithm works

The working of Dijkstra’s algorithm follows a greedy approach—it always picks the node with the smallest known distance and expands from there.

Let’s see how it works step-by-step with this example graph:

This is a weighted graph with nodes A, B, C, D, E, and F, joined by edges that carry non-negative weights. We’ll use Dijkstra algorithm to find the shortest route from A (source node) to every other node in the graph.

Step 1: Initialization

First, the initial distances from the source node (A) to all other nodes in the graph are established. The distance from the source to itself is set to 0, while the distances to all remaining nodes (B, C, D, E, F) are initialized to infinity (∞), indicating that they are not yet reachable. The algorithm then begins its exploration from the source node.

Step 2: Processing Node A

From node A, the algorithm examines all directly connected neighbors. Node A has edges to nodes B and C, each with a weight of 4. The tentative distances to these nodes are calculated as follows:

• Distance to B = 0 + 4 = 4
• Distance to C = 0 + 4 = 4

Since these distances are smaller than their previous values (∞), they are updated. The remaining nodes (D, E, F) retain their initial distances of ∞.

Step 3: Processing Node B

Next, the algorithm selects the unvisited node with the smallest known distance. Both B and C have a distance of 4, so the algorithm may choose either; suppose it selects B.

From node B, the algorithm inspects its unvisited neighbors. B connects to C with an edge of weight 2. The tentative distance to C through B is 4 + 2 = 6.

Since 6 is greater than C’s current distance (4), no update is made. The algorithm then proceeds to the next unvisited node with the smallest distance, which is C.

Step 4: Processing Node C

From node C (distance 4), the algorithm examines its unvisited neighbors: D, E, and F. The tentative distances are calculated as:

• Distance to D = 4 + 3 = 7
• Distance to E = 4 + 1 = 5
• Distance to F = 4 + 6 = 10

All of these values are smaller than the current distances (∞), so they are updated accordingly.

Step 5: Processing Node E

The next unvisited node having the smallest distance is E (distance 5). From E, the algorithm checks its unvisited neighbors D and F:

• Distance to D via E = 5 + 3 = 8 → not smaller than the current D (7), so no update.
• Distance to F via E = 5 + 3 = 8 → smaller than the current F (10), so F is updated to 8.

Step 6: Processing Node D

The next node with the smallest distance is D (distance 7). Its only unvisited neighbor is F, with an edge weight of 2. The distance to F via D is 7 + 2 = 9. Since 9 is not smaller than the current F (8), no update is made.

Once all nodes have been visited, the algorithm terminates. The final shortest distances from the source node (A) to all other nodes are:

• A = 0
• B = 4
• C = 4
• D = 7
• E = 5
• F = 8

These distances represent the shortest path tree originating from node A, showing the minimum cost to reach every other node in the graph.

Since we’re done understanding how Dijkstra’s algorithm works step-by-step, let’s look at its pseudocode to see how these operations translate into structured logic.

Dijkstra’s algorithm pseudocode

Here’s the general pseudocode for Dijkstra’s algorithm:

function Dijkstra(Graph, source): 
    create distance[] and set all to infinity 
    distance[source] = 0 
    create a priority queue Q 
 
    while Q is not empty: 
        u = vertex in Q with smallest distance 
        remove u from Q 
 
        for each neighbor v of u: 
            alt = distance[u] + weight(u, v) 
            if alt < distance[v]: 
                distance[v] = alt 
                update v in Q with new distance 
 
    return distance[] 

In this pseudocode, we start by setting all node distances to infinity, except for the source node, which is zero. We repeatedly pick the node with the smallest tentative distance, then update its neighbors if a shorter path is found. The process continues until all nodes are visited, giving us the shortest paths from the source.

Next, we’ll translate this pseudocode into a working Python implementation.

Dijkstra algorithm Python implementation

This example shows how to implement Dijkstra’s algorithm in Python:

import heapq 
 
def dijkstra(graph, start): 
    # Initialize distances and priority queue 
    distances = {node: float('inf') for node in graph} 
    distances[start] = 0 
    queue = [(0, start)] 
 
    while queue: 
        current_distance, current_node = heapq.heappop(queue) 
 
        # Skip if we already found a shorter path 
        if current_distance > distances[current_node]: 
            continue 
 
        for neighbor, weight in graph[current_node].items(): 
            distance = current_distance + weight 
            if distance < distances[neighbor]: 
                distances[neighbor] = distance 
                heapq.heappush(queue, (distance, neighbor)) 
 
    return distances 
 
# Example graph 
graph = { 
    'A': {'B': 1, 'C': 4}, 
    'B': {'A': 1, 'C': 2, 'D': 5}, 
    'C': {'A': 4, 'B': 2, 'D': 1}, 
    'D': {'B': 5, 'C': 1} 
} 
 
print(dijkstra(graph, 'A')) 

Copy to clipboard
Copy to clipboard

In this code, we use a dictionary to store distances and a min-heap to efficiently select the next node with the smallest distance. For each node, we update the shortest known distance to its neighbors. The final output shows the shortest path distances from the start node to all others.

Now, let’s analyze the time and space complexity of Dijkstra’s algorithm to understand its performance.

Dijkstra’s algorithm complexity analysis

The time complexity of Dijkstra’s algorithm depends on the data structures we use to represent the graph and manage the priority queue.

When we use an adjacency list along with a min-priority queue (heap), the time complexity is O((V + E) log V), where V indicates the total number of vertices and E indicates the total number of edges. This is because each vertex is processed once, and each edge may require a priority queue update.

In contrast, if we use an adjacency matrix with a simple linear search for the smallest distance, the complexity increases to O(V²), which is less efficient for large or sparse graphs.

On the other hand, the space complexity of Dijkstra algorithm is O(V + E), as we store the graph representation, distance table, and priority queue. We maintain a distance value for each vertex, and the priority queue may hold up to V nodes in the worst case.

Thus, while Dijkstra’s algorithm is highly efficient in terms of time, it also requires sufficient memory to track distances and manage visited nodes effectively—especially for large networks or dense graphs.

Finally, let’s see how Dijkstra algorithm is used in real-world scenarios.

Real-world applications of Dijkstra algorithm

Dijkstra’s algorithm is used extensively in both theoretical and practical applications, including:

• GPS navigation systems: Used to calculate the shortest path between two locations on a map.
• Computer networking: Helps determine the shortest data transmission path (e.g., in routing protocols like OSPF).
• Telecommunications: Used in optimizing signal routing and minimizing latency in communication networks.
• Game development: Enables characters or players to find the shortest route in navigation systems or maps.

These applications prove that Dijkstra algorithm is a popular choice for solving real-world shortest path problems across various fields.

Conclusion

In this guide, we discussed Dijkstra’s algorithm in detail, covering what it is, how it works, and how to implement it in Python. We also analyzed its time and space complexity and explored some of its real-world applications.

Key takeaways:

• Dijkstra’s algorithm calculates the shortest path from a source node to all other nodes in weighted graphs with non-negative edges
• It uses a greedy approach, always selecting the unvisited node with the smallest known distance
• With a min-heap implementation, Dijkstra’s algorithm achieves O((V + E) log V) time complexity, making it highly efficient for most practical applications
• The algorithm powers technologies we use daily—from GPS navigation to network routing protocols

If you want to learn more about implementing Dijkstra’s algorithm in Python, check out the Pass the Technical Interview with Python course on Codecademy.

Frequently asked questions

1. Is Dijkstra a BFS or DFS?

Dijkstra’s algorithm is neither BFS nor DFS, though it shares similarities with BFS in how it explores nodes level by level. Unlike BFS, which explores all neighbors equally, Dijkstra always chooses the unvisited node with the smallest distance first, making it a greedy algorithm specifically optimized for weighted graphs.

2. How is Dijkstra’s algorithm used in GPS navigation?

In GPS systems, Dijkstra algorithm calculates the shortest driving route from a starting location to a destination by evaluating possible roads and choosing the path with the least total distance or time.

3. What’s the difference between Dijkstra’s algorithm & DFS?

Dijkstra’s algorithm finds the shortest weighted path, while Depth-First Search (DFS) explores paths without considering weights. Dijkstra algorithm is used for optimization, while DFS is used for traversal or searching.

4. Is Dijkstra’s algorithm a greedy algorithm?

Yes. Dijkstra algorithm is considered a greedy algorithm because it always selects the next node with the smallest known distance, aiming for local optimization that leads to a global solution.

5. Which data structure is used in Dijkstra’s algorithm?

A priority queue (min-heap) is typically used in Dijkstra’s algorithm to efficiently retrieve the next node with the smallest distance.