Weighted graphs: Dijkstra & A*

Shortest paths with non-negative weights, priority queues, and admissible heuristics. · 11 min read

Concept

On a plain grid every step costs the same, so BFS finds the shortest path. But real maps have weights — some moves cost more (rough terrain, longer roads). Now 'shortest' means cheapest total weight, and BFS isn't enough.

What shortest path means

For a path s -> ... -> t, the total cost is the sum of all edge weights on that path. A shortest path is the minimum-cost path among all possible paths from the source to the target. If every edge has weight 1, this becomes fewest edges and BFS is enough. If weights differ, the algorithm must compare total costs, not just hop counts.

Shortest-path algorithms usually maintain a distance table dist[v]: the best cost discovered so far from the source to v. They also keep a parent[v] or came_from[v] pointer so the final route can be reconstructed after the distances are known.

Dijkstra always expands the cheapest-so-far node (a priority queue ordered by distance), guaranteeing the minimum-cost path. A\ adds a heuristic* — an estimate of the distance still to go — so it leans toward the goal and explores far fewer nodes.

Interactive visualization: Switch to the graph view for weighted edges — step through it frame by frame on this page.

Choosing the shortest-path algorithm

BFS: unweighted graph, single source, fewest edges. O(V+E).
Dijkstra: non-negative weighted graph, single source. O((V+E) log V) with a heap.
A\*: non-negative weighted graph with a goal and an admissible heuristic. Same optimal answer as Dijkstra, often fewer visited nodes.
Bellman-Ford: negative edges allowed, single source, detects negative cycles. O(VE).
Floyd-Warshall: all-pairs shortest paths, small/medium dense graph. O(V^3) time and O(V^2) space.

Dijkstra's invariant

Dijkstra keeps a tentative distance dist[v]: the best cost discovered so far from the start to v. The priority queue always pops the node with the smallest tentative distance.

Dijkstra C++ sketch

const long long INF = 4e18;
vector<long long> dist(n, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;

dist[start] = 0;
pq.push({0, start});

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue; // stale queue entry

    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

The core proof behind Dijkstra

pop u with smallest dist[u] — No unsettled node currently has a cheaper known route.
all edge weights are non-negative — Going through any other unsettled node can only add cost.
therefore dist[u] cannot improve later — Any alternative path would be at least as expensive.
relax every edge u → v — Try improving neighbours through u.

Result: When a node is popped, its shortest distance is final

A* and admissible heuristics

A orders the queue by `f(n)=g(n)+h(n)`: `g(n)` is the exact cost from the start to `n`; `h(n)` estimates the remaining cost to the goal. The heuristic must be admissible (never overestimate) for A to preserve optimality. On a 4-neighbour grid, Manhattan distance is admissible because every move changes row or column by at most one.

Heuristic examples

For a 4-direction grid, Manhattan distance abs(r1-r2)+abs(c1-c2) is admissible. For an 8-direction grid with diagonal moves, Euclidean or octile distance is usually more appropriate. A bad heuristic that overestimates may be faster, but it can lose the optimal-path guarantee.

Optimism keeps the proof safe

h(n) ≤ true remaining cost — The heuristic is optimistic.
f(n)=g(n)+h(n) — Estimated total path cost through n.
A* expands lowest f first — It prefers paths that could still be optimal.
when the goal is popped — No frontier path can beat its true cost.

Result: A* is optimal with an admissible heuristic

Complexity

With adjacency lists, BFS and DFS are O(V+E) because every vertex and edge is considered a constant number of times. Dijkstra and A depend on the priority queue; with a binary heap they are typically `O((V+E) log V)`. A often visits far fewer vertices in practice, but its worst-case bound can still match Dijkstra.