Dijkstra's Shortest Path Algorithm Explained with Examples

By Khaled Md Tuhidul Hossain · 2025-11-05 · Algorithms

If you've ever used Google Maps or wondered how network packets find the fastest route, you've already seen Dijkstra's algorithm in action. It's one of those algorithms that sounds intimidating but is surprisingly straightforward once you see it step by step.

So let's break it down.

Interactive visualization

Use the controls below to step through the algorithm or let it play automatically.

name: dijkstra
input: {"nodes": ["A", "B", "C", "D", "E"], "edges": [["A", "B", 4], ["A", "C", 2], ["B", "D", 3], ["B", "C", 1], ["C", "D", 4], ["C", "E", 5], ["D", "E", 1]], "start": "A"}
speed: 700

What does Dijkstra's algorithm actually do?

Given a graph with weighted edges and a starting node, Dijkstra's algorithm finds the shortest path from that starting node to every other node. The weights represent costs, like distance, time, or bandwidth.

Here's the thing: it only works with non-negative edge weights. If you've got negative weights, you'll need Bellman-Ford instead. But for most real-world problems, non-negative weights are what you're dealing with.

The core idea

The algorithm is greedy. It always picks the unvisited node with the smallest known distance, locks it in, and then checks if going through that node gives a shorter path to its neighbors. That's it. Repeat until you've visited everything.

Think of it like exploring a city. You start at home, check which nearby intersection is closest, walk there, then look around from that new spot. You never backtrack to reconsider a place you've already committed to.

Visualizing the graph

Let's work through a concrete example. Here's our weighted graph:

We want to find the shortest path from A to every other node.

Step-by-step walkthrough

We'll track distances in a table and use a priority queue to always process the closest unvisited node first.

Initial state

Priority queue: [(0, A)]

Step 1: Process A (distance 0)

We look at A's neighbors. B is 4 away, C is 2 away, E is 7 away. All of these are less than infinity, so we update them.

Priority queue: [(2, C), (4, B), (7, E)]

Step 2: Process C (distance 2)

C is closest. From C, we can reach B (2+1=3, which beats 4), D (2+5=7), and E (2+8=10, worse than 7).

Notice B's distance dropped from 4 to 3. We found a better route through C.

Priority queue: [(3, B), (7, D), (7, E)]

Step 3: Process B (distance 3)

From B, we can reach D (3+3=6, which beats 7).

Priority queue: [(6, D), (7, E)]

Step 4: Process D (distance 6)

From D, we can reach E (6+2=8, worse than 7). No updates.

Step 5: Process E (distance 7)

E has no unvisited neighbors. We're done.

The shortest path tree

Here's what the final shortest paths look like:

The shortest path from A to D, for example, is A -> C -> B -> D with a total cost of 6. Not A -> B -> D (which would be 7).

Python implementation

Here's a clean implementation using Python's heapq for the priority queue:

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    # Distance to every node starts at infinity
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}

    # Priority queue: (distance, node)
    pq = [(0, start)]
    visited = set()

    while pq:
        current_dist, current_node = heapq.heappop(pq)

        # Skip if we already found a better path
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node]:
            if neighbor in visited:
                continue

            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                previous[neighbor] = current_node
                heapq.heappush(pq, (new_dist, neighbor))

    return distances, previous


def get_path(previous, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()
    if path[0] != start:
        return []  # No path exists
    return path


# Build the graph from our example
graph = defaultdict(list)
edges = [
    ('A', 'B', 4), ('A', 'C', 2), ('A', 'E', 7),
    ('B', 'D', 3), ('B', 'C', 1),
    ('C', 'D', 5), ('C', 'E', 8),
    ('D', 'E', 2),
]

for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))  # Undirected graph

distances, previous = dijkstra(graph, 'A')

print("Shortest distances from A:")
for node, dist in sorted(distances.items()):
    path = get_path(previous, 'A', node)
    print(f"  {node}: {dist} (path: {' -> '.join(path)})")

Output:

Shortest distances from A:
  A: 0 (path: A)
  B: 3 (path: A -> C -> B)
  C: 2 (path: A -> C)
  D: 6 (path: A -> C -> B -> D)
  E: 7 (path: A -> E)

How the priority queue drives everything

The priority queue is doing the heavy lifting here. By always processing the closest unvisited node, we guarantee that once we visit a node, we've already found the shortest path to it. That's the greedy property that makes this work.

Time and space complexity

Time complexity: O((V + E) log V) when using a binary heap priority queue. Every node gets pushed and popped from the heap (O(V log V)), and every edge triggers a potential push (O(E log V)).

Space complexity: O(V + E) for storing the graph, distances, and the priority queue.

If you use a Fibonacci heap, you can get O(V log V + E), but honestly nobody does that in practice. The binary heap version is fast enough for nearly everything.

When to use Dijkstra's algorithm

GPS navigation. Finding the fastest route between two locations. Roads are edges, intersections are nodes, and travel times are weights. Every navigation app uses some variant of this.

Network routing. Protocols like OSPF use Dijkstra's algorithm to find the shortest path for data packets. Each router builds a map of the network and runs the algorithm to determine the best next hop.

Game pathfinding. When an NPC needs to navigate a map with varying terrain costs (roads are cheap, swamps are slow), Dijkstra's handles it naturally. For large maps, A* is usually preferred since it adds a heuristic, but Dijkstra's is the foundation A* builds on.

Social networks. Finding the shortest connection between two people. The weights could represent how strong a connection is.

Common pitfalls

Don't use Dijkstra's with negative edge weights. It assumes that once a node is visited, its distance is final. Negative edges break that assumption because a longer path with a negative edge could end up shorter.

Also, watch out for disconnected graphs. If a node is unreachable from your source, its distance stays at infinity. Your code should handle that gracefully.

One more thing: if all edge weights are equal (unweighted graph), you don't need Dijkstra's at all. Plain BFS will give you shortest paths and it's simpler and faster.

Wrapping up

Dijkstra's algorithm is one of those things that clicks once you see the priority queue pattern. You pick the closest unvisited node, update its neighbors, repeat. The priority queue makes sure you're always making the optimal greedy choice.

Now that you understand how it works, try implementing it yourself with a different graph. Change the weights around, add more nodes, see how the shortest paths shift. That's the best way to really internalize it.