Dijkstra's Shortest Path

The problem

You have a map of places (nodes) connected by roads (edges), and every road has a cost — distance, time, fuel or money. What is the cheapest way to get from a starting place to every other place?

BFS can’t answer this, because it counts edges, not costs: a route with 3 cheap roads can beat a route with 1 expensive road. Dijkstra’s algorithm (Edsger Dijkstra, 1956) solves it for graphs whose weights are not negative.

The idea

Keep a table dist[] with the best-known distance to every node. At the start, dist[source] = 0 and every other entry is ∞ (not reached yet).

Then repeat:

1. Pick the unvisited node u with the smallest dist. Its distance is now final — mark it visited.
2. Relax every edge u → v: if going through u is cheaper than what we know, update:

if dist[u] + w(u, v) < dist[v]:
    dist[v] = dist[u] + w(u, v)
    prev[v] = u          # remember how we got here

3. Stop when every reachable node is visited.

Following the prev[] pointers backwards from any node gives the actual shortest path.

Why is the picked distance final?

All weights are ≥ 0. When u has the smallest distance among unvisited nodes, any other route to u would have to pass through some unvisited node first — which is already at least as far away — and edges can only add more cost. So nothing can ever beat dist[u]. This greedy choice is the heart of the algorithm, and also the reason negative weights break it.

Watch it in 3D

In the sample graph, the direct road A→B costs 4, but A→C costs 2 and C→B costs 1. Watch B’s tag: it first becomes d = 4, and then, when C is processed, it drops to d = 3. That update is called relaxation. The orange edges are the current prev[] pointers — together they form the shortest-path tree.

Code (with a priority queue)

import heapq

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2), ('F', 6)],
    'E': [('C', 10), ('D', 2), ('F', 3), ('G', 5)],
    'F': [('D', 6), ('E', 3), ('G', 1)],
    'G': [('E', 5), ('F', 1)],
}

def dijkstra(source):
    dist = {node: float('inf') for node in graph}
    prev = {}
    dist[source] = 0
    pq = [(0, source)]                       # (distance, node)
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)             # closest unvisited node
        if u in visited:
            continue                         # stale entry, skip
        visited.add(u)
        for v, w in graph[u]:
            if d + w < dist[v]:              # relax the edge
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, prev

dist, prev = dijkstra('A')
print(dist)   # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13, 'G': 14}

path, node = [], 'G'
while node:
    path.append(node)
    node = prev.get(node)
print(' -> '.join(reversed(path)))   # A -> C -> B -> D -> E -> F -> G

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main() {
    int n = 7;                                    // A..G = 0..6
    vector<vector<pair<int,int>>> adj(n);         // (neighbour, weight)
    auto addEdge = [&](int a, int b, int w) { adj[a].push_back({b, w}); adj[b].push_back({a, w}); };
    addEdge(0,1,4); addEdge(0,2,2); addEdge(2,1,1); addEdge(1,3,5); addEdge(2,3,8);
    addEdge(2,4,10); addEdge(3,4,2); addEdge(3,5,6); addEdge(4,5,3); addEdge(4,6,5); addEdge(5,6,1);

    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;   // min-heap
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                // stale entry
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
    }
    for (int i = 0; i < n; i++) cout << char('A' + i) << ": " << dist[i] << "\n";
}

Where is it used?

• Maps and navigation (Google Maps uses advanced descendants such as A* and contraction hierarchies).
• Internet routing: the OSPF protocol runs Dijkstra on every router.
• Games: path-finding for characters (A* is Dijkstra plus a distance guess).
• Network design, flight booking, robot motion planning.

Related algorithms

Common mistakes

• Using it with negative edge weights.
• Marking a node visited when it is pushed instead of when it is popped from the priority queue.
• Forgetting to skip stale queue entries (if d > dist[u]: continue).