Dijkstra Shortest Path Algorithm

Table of Contents +

Think about opening Google Maps. You type where you are and where you want to go. In a moment it shows you the fastest route. How does it pick that one route out of thousands of roads? It uses an idea very close to what we are about to learn. Dijkstra’s algorithm finds the shortest path from one starting point to every other point in a graph. By the end of this page, you will understand the same core idea that route apps rely on.

🗺️ A Real-World Picture

Imagine a small city. Each junction is a point. Each road connects two junctions and has a travel time written on it. You are standing at your home junction. You want to know the shortest time to reach every other junction in the city.

You could try every possible path. But that gets slow fast. There is a smarter way. You always walk to the nearest junction you have not finished with yet. From there you check if the roads going out give you a faster way to reach the neighbours. You keep doing this until every junction is settled. That smart, step-by-step idea is Dijkstra’s algorithm.

The “shortest path” here means the path with the smallest total weight. Weight is just the number written on an edge. It can mean travel time or distance or cost.

🎯 What Dijkstra Actually Does

Dijkstra works on a weighted graph. A weighted graph is a set of vertices joined by edges, where each edge carries a number called its weight.

You give it one starting vertex, called the source. It gives you back the shortest distance from that source to every other vertex.

Here is what it keeps track of as it runs:

  • A distance value for each vertex. This is the best total weight found so far to reach that vertex from the source.
  • A set of vertices that are already finished. Their shortest distance is final and will not change.

At the start the source has distance 0. Every other vertex starts at infinity, because we have not found any path to them yet.

Note

We use infinity as a placeholder that means “no path found yet”. In real code we just use a very large number for it.

🧩 The Core Idea: Relaxation

The whole algorithm rests on one small move called relaxation. Relaxation means checking if going through one vertex gives a shorter way to reach its neighbour.

Say you are at vertex u and its current distance is dist[u]. There is an edge from u to v with weight w. You ask one question. Is dist[u] + w smaller than the distance we already have for v?

If yes, you found a better path. So you update dist[v] to dist[u] + w. If no, you leave v alone.

That is it. You repeat this little check across the graph in a careful order, and the shortest distances all become correct.

🔢 The Small Graph We Will Solve

Let us use a tiny graph so you can see every step. Five vertices named 0, 1, 2, 3, 4. The numbers on the edges are weights.

4

1

2

5

1

3

0

1

2

3

4

We start from vertex 0. We want the shortest distance from 0 to every other vertex. See how vertex 1 can be reached directly with weight 4? But going 0 to 2 to 1 costs only 1 plus 2, which is 3. Dijkstra will catch that cheaper route for us.

⚙️ How the Algorithm Moves

The key trick is the order in which we pick vertices. We always pick the unfinished vertex with the smallest current distance. To do that quickly we use a min-priority queue. A min-priority queue is a structure that always hands you the smallest item first.

Here is the spoken version of the loop:

  • Put the source in the queue with distance 0.
  • Pull out the vertex with the smallest distance. Call it u.
  • Mark u as finished.
  • Relax every edge going out of u. If a neighbour’s distance improves, push it into the queue with the new distance.
  • Repeat until the queue is empty.

We always settle the closest vertex first, and edges are never negative. So once a vertex is pulled out, its distance is final. That is the rule that makes Dijkstra correct.

📝 Steps to Run Dijkstra

Let us write the steps clearly before we code them.

  1. Create a dist array. Set dist[source] = 0 and every other entry to infinity.
  2. Create a min-priority queue and push the pair (0, source). This means distance 0 to the source.
  3. While the queue is not empty, pull out the pair with the smallest distance. Call its vertex u.
  4. If this pulled-out distance is worse than dist[u], skip it. It is a stale entry, an old value we already beat.
  5. For each edge from u to a neighbour v with weight w, check if dist[u] + w < dist[v].
  6. If it is smaller, update dist[v] = dist[u] + w and push (dist[v], v) into the queue.
  7. When the queue empties, dist holds the shortest distance to every vertex.

💻 Dijkstra in Code

Now let us put it together. The code below stores the graph as an adjacency list. An adjacency list keeps, for each vertex, a list of its neighbours and the edge weights. Then it runs the loop using a min-priority queue and prints the shortest distance from vertex 0 to each vertex.

dijkstra.py
import heapq


def dijkstra(adj, source, n):
    dist = [float("inf")] * n      # shortest distance found so far
    dist[source] = 0


    # Min-heap acts as our min-priority queue: (distance, vertex)
    pq = [(0, source)]


    while pq:
        d, u = heapq.heappop(pq)   # pull out the smallest distance
        if d > dist[u]:
            continue               # stale entry, skip it
        # Relax every edge going out of u
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))


    print("Vertex\tDistance from source")
    for i in range(n):
        print(f"{i}\t{dist[i]}")


n = 5
# adj[u] holds (neighbour, weight) pairs
adj = [[] for _ in range(n)]
adj[0].append((1, 4))
adj[0].append((2, 1))
adj[2].append((1, 2))
adj[2].append((3, 5))
adj[1].append((3, 1))
adj[3].append((4, 3))


dijkstra(adj, 0, n)

The output of the above code will be:

Output
Vertex  Distance from source
0  0
1  3
2  1
3  4
4  7

Look at vertex 1. The direct road from 0 cost 4. But the answer came out 3. That is because the path 0 to 2 to 1 cost 1 plus 2, which is 3. The algorithm found the cheaper route on its own, exactly as we hoped.

⚠️ The One Big Rule

Dijkstra has one strict condition you must respect.

Caution

Dijkstra does NOT work with negative edge weights. The algorithm trusts that once a vertex is settled, its distance is final. A negative edge can break that trust and give you wrong answers. If your graph has negative weights, use the Bellman-Ford algorithm instead.

⏱️ How Fast Is It?

Let V be the number of vertices and E be the number of edges.

Note

With a min-priority queue and an adjacency list, Dijkstra runs in O((V + E) log V) time. The log V part comes from each push and pop on the priority queue. If you use a plain array to pick the smallest vertex instead, it becomes O(V squared), which is fine for small dense graphs.

Here is a quick summary you can keep.

Setup Time Complexity When to use
Min-priority queue + adjacency list O((V + E) log V) Most graphs, especially sparse ones
Plain array to pick minimum O(V squared) Small or dense graphs

🐞 Common Mistakes

A few slips trip up most beginners. Watch for these.

  • Using Dijkstra on a graph that has negative edge weights. It will quietly give wrong results.
  • Forgetting to skip stale entries in the priority queue. Without that if d > dist[u] check you do extra work and can even update vertices that are already settled.
  • Marking a vertex finished but then still relaxing edges into it. Once a vertex is settled, leave its distance alone.
  • Starting distances at 0 instead of infinity for non-source vertices. Then every comparison looks “good enough” and nothing updates correctly.

🧩 What You’ve Learned

  • ✅ Dijkstra finds the shortest path from one source vertex to every other vertex in a weighted graph.
  • ✅ It keeps a best-known distance for each vertex and always settles the closest unfinished vertex first.
  • ✅ Relaxation is the core move: check if going through u gives a shorter way to reach a neighbour, and update if it does.
  • ✅ A min-priority queue lets you pull out the closest vertex quickly, giving O((V + E) log V) time.
  • ✅ Dijkstra needs non-negative edge weights; for negative edges you reach for Bellman-Ford instead.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does Dijkstra's algorithm compute?

    Why: Dijkstra finds the shortest distance from a single source vertex to every other vertex in the graph.

  2. 2

    What is 'relaxation' in Dijkstra's algorithm?

    Why: Relaxation checks whether dist[u] + w is smaller than the neighbour's current distance and updates it when it is.

  3. 3

    Why does Dijkstra fail with negative edge weights?

    Why: Once Dijkstra settles a vertex it never revisits it, but a negative edge could later offer a cheaper path, breaking that assumption.

  4. 4

    Which data structure lets Dijkstra pick the closest unfinished vertex efficiently?

    Why: A min-priority queue always hands back the vertex with the smallest current distance, which is exactly what Dijkstra needs.

Score: 0 / 4

🚀 What’s Next?

Previous Topological Sort Next Union-Find (Disjoint Set)

Share & Connect

Share on LinkedIn