What Is Dijkstra’s Algorithm and Implementing the Algorithm through a Complex Example

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.

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.

Get the Skills to Ace a Cybersecurity InterviewCyber Security Expert Master's ProgramStart Learning

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.

Master In-Demand Cyber Security Skills!Cyber Security Expert Master's ProgramLearn Now

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

Step 2: Visit Node A

Neighbours of A:

• B with weight 4
• C with weight 1

Relax edges:

dist[B] = 4
dist[C] = 1

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

Step 4: Visit Node B

Neighbors:

• E with weight 4

Relaxation:

dist[E] = 3 + 4 = 7

Step 5: Visit Node D

Neighbor:

• E with weight 4

Relaxation:

dist[E] = min(7, 5 + 4) = 7

No change.

Final Distance Table

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.

Go from Beginner to Expert in 6 Months!Advanced Executive Program in CybersecurityExplore Program

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:

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.

Make the Switch to a Cybersecurity CareerAdvanced Executive Program in CybersecurityExplore Program

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.