What is the difference between Dijkstra's algorithm and A*?

A* is Dijkstra's algorithm plus a heuristic that estimates the remaining distance to a specific goal. Dijkstra explores outward in all directions equally; A* uses the heuristic to steer the search toward the target, so it usually settles far fewer nodes. With a heuristic of zero, A* is exactly Dijkstra. Dijkstra is best when you need distances to many destinations; A* when you have a single goal and a good heuristic.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 01 / DIJKSTRA'S SHORTEST PATH

The Last Mile.

Watch the explainer

Every map app, every router, every game's pathfinding runs some flavour of this. But you won't watch it. You'll drive it — lose to your own instincts, then meet the courier who never does.

THE GIST · 20 SECONDS

Dijkstra's algorithm finds the shortest path from a starting point to every other point in a weighted graph — a network where each connection has a cost (here, minutes of traffic). Its one idea: always expand the cheapest-known point first, and the moment you reach a point that way, its shortest distance is locked in forever. That's it. It's how maps route you, how the internet routes packets, and how game characters find their way.

Nodean intersection / point
Edgea street between two nodes
Weightthe cost to cross an edge
Frontieropen nodes, cheapest-first (a priority queue)
Relaxfound a cheaper route → lower a node's distance
Settlelock a node — its distance is now final

① Drive by instinct → ② Watch the Dispatcher flood the city → ③ Predict the next lock → ④ Break it with a negative street

YOUR RUN 0min

Depot Drop-off Street · traffic = minutes

Text version of the city map (for screen readers & keyboard)

UNDER THE HOOD

What you just played, written down

You drove it, watched the flood, and predicted the next lock. Here's the same thing as an algorithm — it should read like subtitles to a movie you've already seen.

How the Dispatcher thinks — five steps

Set distances. The start is 0; every other node is ∞ (unknown).
Open the start. Put it in a priority queue keyed by best-known distance.
Pop the cheapest. Take the open node with the smallest distance — call it current.
Relax neighbours. For each street out of current, if reaching the neighbour through current is cheaper than its best-known distance, lower it.
Settle & repeat. Lock current — its distance is now final — and loop until the queue empties (or you've settled the goal).

WHY IT'S CORRECT

Because no street costs less than zero, the instant a node is popped as the cheapest open node, no other path could ever reach it more cheaply. So its distance is safe to lock. That single guarantee is the whole algorithm — and exactly the law you saw in the game.

The algorithm

function dijkstra(graph, start):
    dist[start] = 0
    for every other node v: dist[v] = ∞
    pq = min-priority-queue seeded with (0, start)

    while pq not empty:
        (d, u) = pq.pop_min()        # cheapest open node
        if u is settled: continue
        settle(u)                    # dist[u] is now final
        for each edge (u → v, w):
            if dist[u] + w < dist[v]:  # relaxation
                dist[v] = dist[u] + w
                prev[v] = u
                pq.push((dist[v], v))

    return dist, prev                # prev rebuilds the path

TIME O((V + E) log V) with a binary-heap queue · V nodes, E edges

SPACE O(V) distances, predecessors, and the queue

Solved by hand — the exact trace for the city above

Every lock in order, with the best-known distance at the moment it settled. This is precisely what the loop above does, run on the map you just played.

⚠ When it breaks

Dijkstra trusts that locking is final — which is only true with non-negative weights. Add a single negative edge and a cheaper path can appear after a node is already settled, quietly corrupting the answer; a negative cycle makes the shortest path undefined (−∞) entirely. (In Act 4 — Break it you make one street pay you and watch a finite-but-wrong answer, then make it pay both ways for the −∞ cycle Dijkstra never notices.)

↔ Its cousins

Bellman-Ford handles negative edges (slower: O(V·E)). Add a goal-direction heuristic and Dijkstra becomes A*, which aims the flood as a beam instead of spreading everywhere. BFS is just Dijkstra when every weight is 1.

★ Where you've used it

Turn-by-turn navigation (Maps), internet routing (OSPF / IS-IS), NPC and unit pathfinding in games, network-latency planning, and plenty of "cheapest way from A to B" puzzles.

The picture: settling nodes by distance

The example graph from the page’s code. Each box shows the final distance and the order the node was locked (#1 is the start). The highlighted route costs 8. The direct road home → a (4) is never used: by the time a is popped, the detour through b has already lowered it to 3.

Worked example, step by step

The graph is home → a (4), home → b (2), b → a (1), b → c (7), a → c (3), c → shop (2), start home, goal shop. The queue holds (distance, node) pairs and is read smallest first. A node can be pushed more than once; an old entry is skipped when it comes back.

Pop	Entry	Action	Pushed (improved)	Distances after
1	(0, home)	settle	a=4, b=2	home:0 a:4 b:2 c:Infinity shop:Infinity
2	(2, b)	settle	a=3, c=9	home:0 a:3 b:2 c:9 shop:Infinity
3	(3, a)	settle	c=6	home:0 a:3 b:2 c:6 shop:Infinity
4	(4, a)	stale: already settled, skip	—	—
5	(6, c)	settle	shop=8	home:0 a:3 b:2 c:6 shop:8
6	(8, shop)	settle	nothing cheaper	home:0 a:3 b:2 c:6 shop:8
7	(9, c)	stale: already settled, skip	—	—

Rows 4 and 7 (highlighted) are stale entries: a was first pushed at 4, then improved to 3 through b, and the old (4, a) still sits in the queue. Popping it is harmless as long as the code checks that the node is already settled. The same happens to c, queued at 9 and then at 6. The answer is 8, along home → b → a → c → shop, found in 7 pops for 5 nodes and 6 edges. Notice the order: 0, 2, 3, 6, 8. Distances come off the queue in non-decreasing order, which is the invariant that makes locking safe.

Complexity and trade-offs

Case	Time	Space	Why
Binary heap, lazy deletion	`O((V + E) log V)`	`O(E)` queue, `O(V)` arrays	Each edge can push one entry, each push and pop costs `log` of the queue size. The stale entries above are the price of not having a decrease-key.
Array scan (the page’s Python)	`O(V²)`	`O(V)`	Finds the minimum by looping over all nodes, V times. No heap, so no log factor; better than the heap when E is close to V².
Fibonacci heap	`O(E + V log V)`	`O(V)`	Best asymptotic bound. Large constants and hard to implement, so binary heaps usually win in practice.
BFS	`O(V + E)`	`O(V)`	Valid only when every edge costs the same. A plain queue replaces the priority queue.
Bellman-Ford	`O(V·E)`	`O(V)`	Slower, but accepts negative edges and detects negative cycles. See the failure case below.

The choice between the first two rows is about density. A road network has E close to a small multiple of V, so the heap version is far ahead. A complete graph has E near V², where the heap version is O(V² log V) and the plain scan is O(V²). Stopping when the goal is popped (not pushed) saves work on a single-target query: in the example, the goal pops on pop 6 of 7. For many queries on a fixed map, preprocessing methods beat running Dijkstra each time, but they all rest on this same settling rule.

Common mistakes

Running it with a negative edge
Graph s → a (2), s → b (5), b → a (−4), a → t (1). Dijkstra settles a at 2 before it looks at b, relaxes a → t to 3, and never expands a again when b later lowers it. It returns dist[t] = 3. The real shortest route is s → b → a → t = 2, which Bellman-Ford finds. A single negative edge breaks the “settled means final” rule.
Stopping when the goal is first pushed
Graph s → g (10), s → a (1), a → g (2). The goal is pushed with 10 while expanding s. Returning then gives 10, but the true answer is 3, found only after a is popped. Check for the goal when it is popped.
Not skipping stale queue entries
Without the “already settled” check the answer stays right but every outdated entry is expanded again. On a 40-node graph where each node has an edge to every later one, the loop examines 780 edges with the check and 9919 without it: the extra work re-scans edges that cannot improve anything.
Storing a two-way street in one direction only
A two-way street needs an entry in both adjacency lists. With only home → a (4) and b → home (2) stored, dist[b] stays Infinity from home, which looks like “unreachable”, not like a bug. Print unreachable nodes when testing.
Treating the unreachable case as a distance
If the goal is not connected, the distance array still holds its initial infinity. Returning it as a number, or adding to it, produces nonsense such as Infinity + 2. Check for it and return an explicit “no route”.

Where this shows up

Route planning
Roads become edges weighted by travel time, intersections become nodes. Production routers add precomputation or goal-directed search on top, but the settling rule is the one shown here.
Link-state network routing
Link-state routing protocols such as OSPF and IS-IS have every router build a map of the network and run a shortest-path-first computation over it to fill its forwarding table.
Games and simulation
Movement costs differ by terrain (road, mud, water), so unit pathfinding needs weighted shortest paths. Dijkstra from one source also gives a “distance to everything” map in one pass, handy for area-of-effect and AI decisions.
A building block for other algorithms
It is the inner loop of Johnson’s all-pairs method and of many minimum-cost problems. With a goal-direction heuristic it becomes A*, covered on its own page.

RUN IT YOURSELF

Dijkstra's algorithm, in Python & TypeScript

The same shortest-path search in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).

HOW TO READ THE CODE — 4 IDEAS

Every node starts at distance infinity, except the source at 0 (step 1).
Repeatedly settle the nearest not-yet-settled node — its distance is now final (step 2).
Relax each edge out of it: if going through it is cheaper, lower the neighbour's distance (step 3).
Once the goal is settled, its distance is the cheapest total cost (step 4). Needs non-negative weights.

CPython · WebAssembly

# Dijkstra: cheapest path with non-negative edge weights. Settle
# the nearest unsettled node each round. O(V^2) here for clarity.

def dijkstra(graph, start, goal):
    # STEP 1 - best known distance to each node: start 0, rest infinity.
    INF = float("inf")
    dist = {node: INF for node in graph}
    dist[start] = 0
    settled = set()

while len(settled) < len(graph):
        # STEP 2 - pick the unsettled node with the smallest distance.
        unsettled = (n for n in graph if n not in settled)
        node = min(unsettled, key=lambda n: dist[n])
        if dist[node] == INF:
            break                      # remaining nodes are unreachable
        settled.add(node)

# STEP 3 - relax edges: reach any neighbour more cheaply?
        for nbr, weight in graph[node].items():
            if dist[node] + weight < dist[nbr]:
                dist[nbr] = dist[node] + weight

# STEP 4 - the settled distance to the goal is optimal.
    return dist[goal]

roads = {
    "home": {"a": 4, "b": 2}, "a": {"c": 3}, "b": {"a": 1, "c": 7},
    "c": {"shop": 2}, "shop": {},
}
print("cheapest home -> shop:", dijkstra(roads, "home", "shop"))

// Dijkstra: cheapest path with non-negative edge weights. Settle
// the nearest unsettled node each round. O(V^2) here for clarity.
type Weighted = Record<string, Record<string, number>>;

function dijkstra(graph: Weighted, start: string, goal: string): number {
  // STEP 1 - best known distance to each node: start 0, rest Infinity.
  const dist: Record<string, number> = {};
  for (const node of Object.keys(graph)) dist[node] = Infinity;
  dist[start] = 0;
  const settled = new Set<string>();

while (settled.size < Object.keys(graph).length) {
    // STEP 2 - pick the unsettled node with the smallest distance.
    let node = "";
    let best = Infinity;
    for (const n of Object.keys(graph)) {
      if (!settled.has(n) && dist[n] < best) { best = dist[n]; node = n; }
    }
    if (best === Infinity) break;        // remaining nodes are unreachable
    settled.add(node);

// STEP 3 - relax edges: reach any neighbour more cheaply?
    for (const [nbr, weight] of Object.entries(graph[node])) {
      if (dist[node] + weight < dist[nbr]) dist[nbr] = dist[node] + weight;
    }
  }

// STEP 4 - the settled distance to the goal is optimal.
  return dist[goal];
}

const roads: Weighted = {
  home: { a: 4, b: 2 }, a: { c: 3 }, b: { a: 1, c: 7 },
  c: { shop: 2 }, shop: {},
};
console.log("cheapest home -> shop:", dijkstra(roads, "home", "shop"));

▶ Watch it explained

Dijkstra's Algorithm: Time and Space Complexity, From First Principles

QUICK CHECK

Did it stick?

See every answer, with the reasoning

When Dijkstra pops a node from the priority queue, its shortest distance is…
Answer: final — it can never improve later — That’s the invariant: with non-negative weights, the cheapest open node can’t be beaten, so it’s locked.
Which node does Dijkstra always expand next?
Answer: the unsettled node with the smallest known distance — It always drains the cheapest open node first — that’s the “pop” you predicted in Act 3.
Dijkstra can return wrong answers when the graph has…
Answer: negative edge weights — A negative edge can make a cheaper path appear after a node is settled — exactly what you triggered in Act 4. Use Bellman-Ford instead.

FAQ

Dijkstra's algorithm, answered

What is Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path from one starting node to every other node in a weighted graph with non-negative edge weights. It always expands the closest unvisited node first, locking in each node's shortest distance one at a time. Published by Edsger W. Dijkstra in 1959, it's the backbone of map navigation, network routing and game pathfinding.

How does Dijkstra's algorithm work?

It keeps a tentative distance to every node (0 for the start, ∞ for the rest) in a min-priority queue. It repeatedly pops the closest unsettled node, marks it settled (its distance is now final), and relaxes each neighbour — lowering its distance if the route through the current node is cheaper. This repeats until the queue is empty or the destination is settled. Play Acts 1–3 above to watch it happen.

What is the time complexity of Dijkstra's algorithm?

With a binary-heap priority queue it runs in O((V + E) log V) time (V vertices, E edges). A plain array version is O(V²) — sometimes faster on dense graphs — and a Fibonacci heap reaches O(E + V log V). Space complexity is O(V).

Why doesn't Dijkstra's algorithm work with negative edge weights?

Dijkstra assumes that once a node is settled, no cheaper path to it can ever appear — which is only true when every edge is non-negative. A negative edge can reveal a cheaper route to an already-settled node after the fact, and a negative cycle makes the shortest path undefined (−∞). Use the Bellman-Ford algorithm for negative edges. (Try Act 4 — Break it — to see this happen live.)

What's the difference between Dijkstra's algorithm and BFS?

BFS finds the path with the fewest edges on an unweighted graph using a FIFO queue. Dijkstra finds the lowest-total-weight path on a weighted graph using a priority queue. Dijkstra reduces to BFS when every edge weight is equal — BFS is just the case where all weights are 1.

Is Dijkstra's algorithm greedy or dynamic programming?

It's a greedy algorithm: each step commits to the closest unsettled node and never reconsiders. The non-negative-weight invariant is what makes that greedy choice provably correct.

Dijkstra vs A* — what's the difference?

A* is Dijkstra plus a heuristic that estimates the remaining distance to a single goal, so it steers the search toward the target and settles far fewer nodes. With a zero heuristic, A* is Dijkstra. Use Dijkstra for distances to many destinations; A* for one goal with a good heuristic.

Where is Dijkstra's algorithm used in real life?

Turn-by-turn navigation (Google/Apple Maps), internet routing protocols (OSPF, IS-IS), character and unit pathfinding in games, network traffic engineering, and logistics "cheapest route" problems.

Finished this one? 0 / 99 Algorithms done

NextA* Search: The Ascent Next on the “The cheapest way across” ladder · rung 2 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more

Challenges →