# Dijkstra's Shortest Path, From Scratch

> Dijkstra's algorithm taught from intuition: why BFS breaks once edges have weights, the greedy 'always expand the closest node' idea, a priority-queue implementation walked step by step across seven languages, and where it runs the real world - maps, routing, and A*.


---

# Dijkstra's Shortest Path, From Scratch

Every time a map app draws a fastest route, something very close to Dijkstra's algorithm is running
underneath. It answers one of the most useful questions in computing: given a network of places connected by
roads of different lengths, what is the cheapest way from here to there?

If you have met [BFS and graphs already](/guides/graph-theory-whats-connected-to-what/2), you have most of
the intuition. BFS finds the shortest path when every step costs the same. The moment steps have different
costs - a highway versus a side street - BFS gives the wrong answer, and Dijkstra is the fix. This guide
builds it from that gap.

Every example runs in Python right in the page, so you can watch the distances settle as it runs.

## How to read this

Read in order. Phase 1 shows exactly where BFS breaks and names the greedy idea that repairs it; phase 2
turns that idea into real code with a priority queue; phase 3 is where it lives in production, plus the one
input that quietly breaks it.

## The phases

1. **[Why BFS Isn't Enough for Weighted Graphs](01-why-bfs-isnt-enough.md)** 🟢 Basic - how a fewest-hops
   search picks a long road over a short detour, and the "always expand the closest unvisited node" idea that
   fixes it.
2. **[Dijkstra with a Priority Queue](02-dijkstra-with-a-priority-queue.md)** 🟡 Intermediate - the full
   algorithm, walked step by step, implemented with a min-heap across seven languages.
3. **[Where Dijkstra Runs the World](03-where-dijkstra-runs-the-world.md)** 🟡 Intermediate - maps and network
   routing, A* as Dijkstra plus a heuristic, and why a single negative edge weight breaks the whole thing.


---

# Why BFS Isn't Enough for Weighted Graphs

Breadth-first search finds the shortest path in an unweighted graph by exploring outward one hop at a time -
the first time it reaches a node, it got there by the fewest edges. (If that is new, the
[graph theory guide](/guides/graph-theory-whats-connected-to-what/2) walks through BFS first.) That guarantee
quietly depends on one assumption: every edge costs the same. Break that assumption and BFS breaks with it.

## Where "fewest hops" goes wrong

Picture three intersections. From `A` you can take a direct road to `C` that is long (weight 10), or a short
hop to `B` (weight 1) and another short hop from `B` to `C` (weight 1). The direct road is one hop; the
detour is two. BFS counts hops, so it happily reports the one-hop road - the *longer* route.

```python runnable
from collections import deque

# weighted graph: node -> list of (neighbor, weight)
graph = {
    "A": [("B", 1), ("C", 10)],
    "B": [("C", 1)],
    "C": [],
}

def bfs_fewest_hops(graph, start, target):
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == target:
            return path
        for neighbor, _weight in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    return None

def path_weight(graph, path):
    total = 0
    for a, b in zip(path, path[1:]):
        for neighbor, weight in graph[a]:
            if neighbor == b:
                total += weight
    return total

path = bfs_fewest_hops(graph, "A", "C")
print("BFS route:", path, "with total weight", path_weight(graph, path))
```
```console
BFS route: ['A', 'C'] with total weight 10
```
*What just happened:* BFS returned `A -> C`, one hop, and threw the weights away entirely. Its actual cost is
10, while the two-hop route `A -> B -> C` costs only `1 + 1 = 2`. BFS is not buggy - it is answering "fewest
edges," which is simply the wrong question once edges have different costs.

📝 **Terminology.** A **weighted graph** attaches a number - a *weight* or *cost* - to each edge: distance,
travel time, price, whatever you are minimizing. The **shortest path** is the route with the smallest total
weight, not the fewest edges.

## The greedy idea that fixes it

Dijkstra keeps a running best-known distance to every node, all starting at infinity except the start, which
is 0. Then it repeats one move:

> Of all the nodes you have not finalized yet, take the one with the smallest known distance. Finalize it, and
> use its edges to try to improve its neighbors' distances.

The magic is in *why finalizing is safe*. When you pull out the unvisited node with the smallest tentative
distance, no other route to it can be shorter - any alternative would have to pass through some other
unvisited node that is already *farther* away, so it could only add cost. That is the key insight, and it is
exactly the assumption a negative edge would violate (phase 3).

```
Start: distance to A is 0, everything else is infinity.
Expand the closest unvisited node. Relax its edges (lower a neighbor's distance if you found a cheaper route).
Repeat, always taking the closest unfinalized node, until every reachable node is finalized.
```

💡 **Key point.** BFS also "expands the closest node" - but when every edge weight is 1, "closest" and
"fewest hops" are the same thing, which is exactly why BFS is just Dijkstra on an unweighted graph. Dijkstra
generalizes BFS from counting hops to summing weights.

Walk the earlier graph by hand: `A` is closest (0), so finalize it and set `B` to 1 and `C` to 10. Now the
closest unfinalized node is `B` at 1; finalize it, and its edge to `C` offers `1 + 1 = 2`, which beats 10, so
`C` drops to 2. Finalize `C` at 2. The detour wins, exactly as it should. Phase 2 makes this loop into code.

## Check yourself

```quiz
[
  {
    "q": "Why can BFS return the wrong route once edges have weights?",
    "choices": ["BFS cannot run on weighted graphs at all", "BFS counts hops, so it can pick a one-hop road of weight 10 over a two-hop route of weight 2", "BFS always returns the longest path", "Weights make BFS loop forever"],
    "answer": 1,
    "explain": "BFS minimizes the number of edges, not the total weight. When a single long edge beats a multi-edge shortcut on hop count, BFS chooses it despite the higher cost."
  },
  {
    "q": "On each step, which node does Dijkstra expand next?",
    "choices": ["A random unvisited node", "The unvisited node with the smallest known distance from the start", "The node with the most neighbors", "The target node first"],
    "answer": 1,
    "explain": "Dijkstra is greedy on distance: it always finalizes the closest unvisited node, because no shorter route to it can exist through the still-farther nodes."
  },
  {
    "q": "When every edge weight is 1, how does Dijkstra behave?",
    "choices": ["Like DFS", "Like BFS", "Like a random walk", "Like binary search"],
    "answer": 1,
    "explain": "With equal weights, 'closest unvisited node' is identical to 'fewest hops', which is exactly what BFS computes. Dijkstra is the weighted generalization of BFS."
  }
]
```


---

# Dijkstra with a Priority Queue

Phase 1 gave the loop in words: repeatedly take the closest unfinalized node and use its edges to improve its
neighbors. The one piece that needs care is "take the closest node." Scanning every node each round works but
is slow. A **min-priority-queue** - a min-heap - hands you the smallest-distance node in `O(log n)`, and that
is what makes Dijkstra fast enough to route traffic in real time.

## The data structures

- `dist` - a dictionary mapping each node to its best-known distance from the start. Everything begins at
  infinity except the start at 0.
- A **min-heap** `pq` of `(distance, node)` pairs. Python's `heapq` keeps the smallest pair on top, and
  because the distance is first, "smallest pair" means "closest node."

## The algorithm, step by step

```python runnable
import heapq

graph = {
    "A": [("B", 1), ("C", 10)],
    "B": [("C", 1), ("D", 5)],
    "C": [("D", 1)],
    "D": [],
}

def dijkstra(graph, start):
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    pq = [(0, start)]                      # (distance, node), min-heap by distance
    while pq:
        d, node = heapq.heappop(pq)        # closest unfinalized node
        if d > dist[node]:
            continue                       # stale entry - we already found a shorter route
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:  # relax: found a cheaper way to neighbor
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

print(dijkstra(graph, "A"))
```
```console
{'A': 0, 'B': 1, 'C': 2, 'D': 3}
```
*What just happened:* trace the heap. It starts with `(0, A)`. Popping `A` relaxes its edges, pushing
`(1, B)` and `(10, C)`. Next the heap yields `(1, B)` - the closest node - and `B`'s edge to `C` offers
`1 + 1 = 2`, beating 10, so `C` drops to 2 and `(2, C)` is pushed; `B` also sets `D` to 6. Then `(2, C)` pops
and improves `D` to `2 + 1 = 3`. When the old `(6, D)` and `(10, C)` finally surface, the guard
`d > dist[node]` throws them away as stale. Final distances: `B` is 1, `C` is 2, `D` is 3.

📝 **Terminology.** *Relaxing* an edge `(u, v)` means: if `dist[u] + weight(u, v)` is less than the current
`dist[v]`, lower `dist[v]` to that new, cheaper value. The whole algorithm is just relaxing edges in the
right order - closest node first.

💡 **Key point: the stale-entry skip.** A plain binary heap has no "decrease-key," so instead of updating an
existing entry we just push a new, smaller `(distance, node)`. That leaves outdated pairs in the heap. The
`if d > dist[node]: continue` line quietly discards them: if the distance we popped is worse than the best we
have already recorded, this entry is old news. This lazy approach is simpler than a decrease-key heap and
runs in `O((V + E) log V)`.

## Getting the path, not just the distance

Distances are often not enough - you want the actual route. Track each node's predecessor as you relax, then
walk the predecessors backward from the target.

```python runnable
import heapq

graph = {
    "A": [("B", 1), ("C", 10)],
    "B": [("C", 1), ("D", 5)],
    "C": [("D", 1)],
    "D": [],
}

def shortest_path(graph, start, target):
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            nd = d + weight
            if nd < dist[neighbor]:
                dist[neighbor] = nd
                prev[neighbor] = node
                heapq.heappush(pq, (nd, neighbor))
    # rebuild the route by following predecessors backward
    path, cur = [], target
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    path.reverse()
    return path, dist[target]

print(shortest_path(graph, "A", "D"))
```
```console
(['A', 'B', 'C', 'D'], 3)
```
*What just happened:* every time a node's distance improved, we recorded *which* node we came from in `prev`.
Starting at `D` and following `prev` gives `D -> C -> B -> A`; reversing it yields the route `A -> B -> C -> D`
with total weight 3 - the same cheap detour the intuition predicted.

## The same algorithm, in other languages

The moving parts never change: a `dist` map, a min-heap of `(distance, node)`, pop the closest, skip stale
entries, relax edges. What changes is how each language spells "min-heap" - Python's `heapq`, Java's
`PriorityQueue`, C++'s `priority_queue` with `greater`, Go's `container/heap`, Rust's `BinaryHeap` with
`Reverse`. Flip through the tabs.

[[codegroup Dijkstra]]

```python
import heapq

def dijkstra(graph, start):
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            nd = d + weight
            if nd < dist[neighbor]:
                dist[neighbor] = nd
                heapq.heappush(pq, (nd, neighbor))
    return dist
```

```javascript
class MinHeap {
  constructor() { this.items = []; }
  get size() { return this.items.length; }
  push(item) {
    const a = this.items;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let small = i;
        if (l < a.length && a[l][0] < a[small][0]) small = l;
        if (r < a.length && a[r][0] < a[small][0]) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}

function dijkstra(graph, start) {
  const dist = {};
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;
  const pq = new MinHeap();
  pq.push([0, start]);
  while (pq.size > 0) {
    const [d, node] = pq.pop();
    if (d > dist[node]) continue;
    for (const [neighbor, weight] of graph[node]) {
      const nd = d + weight;
      if (nd < dist[neighbor]) {
        dist[neighbor] = nd;
        pq.push([nd, neighbor]);
      }
    }
  }
  return dist;
}
```

```typescript
type Graph = Record<string, [string, number][]>;

class MinHeap {
  private items: [number, string][] = [];
  get size(): number { return this.items.length; }
  push(item: [number, string]): void {
    const a = this.items;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop(): [number, string] {
    const a = this.items;
    const top = a[0];
    const last = a.pop()!;
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let small = i;
        if (l < a.length && a[l][0] < a[small][0]) small = l;
        if (r < a.length && a[r][0] < a[small][0]) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}

function dijkstra(graph: Graph, start: string): Record<string, number> {
  const dist: Record<string, number> = {};
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;
  const pq = new MinHeap();
  pq.push([0, start]);
  while (pq.size > 0) {
    const [d, node] = pq.pop();
    if (d > dist[node]) continue;
    for (const [neighbor, weight] of graph[node]) {
      const nd = d + weight;
      if (nd < dist[neighbor]) {
        dist[neighbor] = nd;
        pq.push([nd, neighbor]);
      }
    }
  }
  return dist;
}
```

```java
import java.util.*;

record Edge(String to, int weight) {}

static Map<String, Integer> dijkstra(Map<String, List<Edge>> graph, String start) {
    record State(int dist, String node) {}
    Map<String, Integer> dist = new HashMap<>();
    for (String node : graph.keySet()) dist.put(node, Integer.MAX_VALUE);
    dist.put(start, 0);
    PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingInt(State::dist));
    pq.add(new State(0, start));
    while (!pq.isEmpty()) {
        State cur = pq.poll();
        if (cur.dist() > dist.get(cur.node())) continue;
        for (Edge e : graph.get(cur.node())) {
            int nd = cur.dist() + e.weight();
            if (nd < dist.get(e.to())) {
                dist.put(e.to(), nd);
                pq.add(new State(nd, e.to()));
            }
        }
    }
    return dist;
}
```

```cpp
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>
#include <limits>

std::unordered_map<std::string, int> dijkstra(
    std::unordered_map<std::string, std::vector<std::pair<std::string, int>>>& graph,
    const std::string& start) {
    std::unordered_map<std::string, int> dist;
    for (auto& [node, edges] : graph) dist[node] = std::numeric_limits<int>::max();
    dist[start] = 0;
    using State = std::pair<int, std::string>;   // (distance, node)
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();
        if (d > dist[node]) continue;
        for (auto& [neighbor, weight] : graph[node]) {
            int nd = d + weight;
            if (nd < dist[neighbor]) {
                dist[neighbor] = nd;
                pq.push({nd, neighbor});
            }
        }
    }
    return dist;
}
```

```go
package main

import (
    "container/heap"
    "math"
)

type Edge struct {
    to     string
    weight int
}

type State struct {
    dist int
    node string
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any)        { *pq = append(*pq, x.(State)) }
func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}

func dijkstra(graph map[string][]Edge, start string) map[string]int {
    dist := make(map[string]int)
    for node := range graph {
        dist[node] = math.MaxInt
    }
    dist[start] = 0
    pq := &PriorityQueue{{0, start}}
    heap.Init(pq)
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(State)
        if cur.dist > dist[cur.node] {
            continue
        }
        for _, e := range graph[cur.node] {
            nd := cur.dist + e.weight
            if nd < dist[e.to] {
                dist[e.to] = nd
                heap.Push(pq, State{nd, e.to})
            }
        }
    }
    return dist
}
```

```rust
use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;

fn dijkstra(graph: &HashMap<String, Vec<(String, u32)>>, start: &str) -> HashMap<String, u32> {
    let mut dist: HashMap<String, u32> = graph.keys().map(|k| (k.clone(), u32::MAX)).collect();
    dist.insert(start.to_string(), 0);
    let mut pq = BinaryHeap::new();
    pq.push(Reverse((0u32, start.to_string())));
    while let Some(Reverse((d, node))) = pq.pop() {
        if d > dist[&node] {
            continue;
        }
        for (neighbor, weight) in &graph[&node] {
            let nd = d + weight;
            if nd < dist[neighbor] {
                dist.insert(neighbor.clone(), nd);
                pq.push(Reverse((nd, neighbor.clone())));
            }
        }
    }
    dist
}
```

[[/codegroup]]

Two details worth noticing across the tabs. C++ and Rust make a min-heap out of a max-heap: `std::greater`
flips the comparison, and `Reverse` flips the ordering, because both `priority_queue` and `BinaryHeap` are
max-heaps by default. And every version keeps the distance first in the pair, so "smallest in the heap"
always means "closest node."

## Check yourself

```quiz
[
  {
    "q": "Why does Dijkstra use a min-priority-queue?",
    "choices": ["To sort the final list of distances", "To efficiently pull out the unfinalized node with the smallest tentative distance each round", "To store the graph's edges", "To detect cycles in the graph"],
    "answer": 1,
    "explain": "The core operation is 'expand the closest node.' A min-heap returns that node in O(log n), which is what keeps the whole algorithm fast."
  },
  {
    "q": "What does 'relaxing' an edge (u, v) mean?",
    "choices": ["Removing the edge from the graph", "If dist[u] + weight(u, v) is smaller than dist[v], lowering dist[v] to that value", "Doubling the edge's weight", "Marking v as finalized"],
    "answer": 1,
    "explain": "Relaxation is the update step: whenever going through u gives a cheaper route to v, dist[v] is lowered. Dijkstra is just edge relaxation in closest-first order."
  },
  {
    "q": "In the heap-based version, why skip a popped (d, node) when d > dist[node]?",
    "choices": ["It signals a bug in the graph", "It is a stale, outdated entry - a shorter route to that node was already recorded, so this one is obsolete", "Only to save a little memory", "That situation can never actually happen"],
    "answer": 1,
    "explain": "Without decrease-key, improved distances are pushed as new heap entries, leaving older larger ones behind. If the popped distance is worse than the recorded best, the entry is stale and is discarded."
  }
]
```


---

# Where Dijkstra Runs the World

Dijkstra is not a textbook curiosity - it runs quietly under software you use every day. This phase covers
where it shows up, the small tweak that makes it even faster for point-to-point routing, and the one kind of
input that silently breaks it.

## Where it actually runs

- **Maps and navigation.** Road networks are weighted graphs - intersections are nodes, roads are edges, and
  the weight is travel time (adjusted live for traffic). Finding your route is a shortest-path query. Real
  map engines precompute and layer tricks on top, but the shortest-path core is Dijkstra's idea.
- **Network routing.** Link-state protocols like OSPF have each router build a map of the network and run
  Dijkstra to decide the cheapest next hop for every destination. The packets carrying this page were routed
  by descendants of this algorithm.
- **Anything with a weighted "cheapest route" question.** Flight-fare connections, transit trip planners,
  latency-aware request routing, even pathfinding costs in some games - all shortest-path problems wearing
  different clothes.

## A* : Dijkstra plus a hunch

Plain Dijkstra explores outward in every direction equally, because it has no idea where the target is. If
you are routing to one specific destination, that wastes effort exploring away from the goal. **A*** ("A
star") fixes this with a **heuristic**: an estimate of the remaining distance from each node to the target
(for maps, the straight-line distance). It prioritizes nodes by `distance_so_far + estimated_distance_left`,
so it explores toward the goal first and reaches it sooner. When the heuristic is always 0 - no guess at all -
A* is exactly Dijkstra. As long as the heuristic never *overestimates* the true remaining distance, A* still
returns the genuine shortest path, just faster.

💡 **Key point.** Dijkstra answers "shortest paths to *everywhere*" from one source. A* answers "shortest path
to *this one target*" and uses knowing the target to skip irrelevant exploration. Same skeleton, one extra
term in the priority.

## The gotcha: negative edge weights break it

Dijkstra's correctness rests entirely on the phase-1 promise: when you finalize the closest unvisited node,
no cheaper route to it can exist. A **negative edge weight** destroys that promise - a later edge can *lower*
a total, so a node you already finalized might have had a cheaper path you never reconsidered.

```python runnable
import heapq

# C -> B has a NEGATIVE weight
graph = {
    "A": [("B", 1), ("C", 2)],
    "B": [],
    "C": [("B", -2)],
}

def dijkstra_finalizing(graph, start):
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    visited = set()
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)                 # node is now final - never revisited
        for neighbor, weight in graph[node]:
            if neighbor not in visited and d + weight < dist[neighbor]:
                dist[neighbor] = d + weight
                heapq.heappush(pq, (d + weight, neighbor))
    return dist

print("Dijkstra says:", dijkstra_finalizing(graph, "A"))
print("But A -> C -> B really costs:", 2 + (-2))
```
```console
Dijkstra says: {'A': 0, 'B': 1, 'C': 2}
But A -> C -> B really costs: 0
```
*What just happened:* Dijkstra finalized `B` at distance 1 (the direct `A -> B` edge) and marked it done.
Only afterward did it expand `C`, whose `-2` edge to `B` would have made `A -> C -> B` cost `2 - 2 = 0` -
cheaper. But `B` was already finalized, so that better route was never applied. The reported distance of 1 is
simply wrong; the true answer is 0.

⚠️ **Gotcha.** This failure is silent - no crash, no warning, just a wrong number. Dropping the "finalize
once" rule to keep re-opening nodes does not save you either: with negative weights that can do exponential
work, and a **negative cycle** (a loop whose weights sum below zero) has no shortest path at all, since you
could circle it forever driving the cost down. Do not reach for a "patched" Dijkstra on negative weights.

📝 **Terminology.** For graphs that genuinely have negative edge weights (but no negative cycle), use
**Bellman-Ford**. It relaxes every edge `V - 1` times instead of trusting a greedy finalize order, so it
tolerates negatives and can even detect a negative cycle. It is slower - `O(V * E)` versus Dijkstra's
`O((V + E) log V)` - which is the price of not assuming edges only add cost.

## What we built

- BFS finds shortest paths only when every edge costs the same; weights need Dijkstra.
- Dijkstra greedily finalizes the closest unvisited node and relaxes its edges, using a min-heap to find that
  node fast.
- The stale-entry skip lets a plain heap stand in for a decrease-key heap.
- A* adds a goal-direction heuristic to reach a single target faster; with a zero heuristic it is Dijkstra.
- Negative edges break Dijkstra's core assumption - use Bellman-Ford there.

## Check yourself

```quiz
[
  {
    "q": "What is A* in one line?",
    "choices": ["A faster sorting algorithm", "Dijkstra plus a heuristic estimate of the remaining distance to the goal, so it explores toward the target first", "BFS applied to weighted graphs", "Dijkstra run backward from the target"],
    "answer": 1,
    "explain": "A* prioritizes nodes by distance-so-far plus an estimate of distance-left, steering the search toward one target. With a zero heuristic it reduces exactly to Dijkstra."
  },
  {
    "q": "Why does a negative edge weight break Dijkstra?",
    "choices": ["A min-heap cannot hold negative numbers", "Once Dijkstra finalizes a node it never reconsiders it, but a later negative edge could have created a shorter path to that node", "Negative weights make the graph infinite", "It does not actually break it"],
    "answer": 1,
    "explain": "Finalizing assumes no cheaper route to a settled node can appear later. A negative edge can lower a total after the fact, so the already-finalized distance can be wrong."
  },
  {
    "q": "Which algorithm correctly handles a graph with negative edge weights but no negative cycle?",
    "choices": ["Binary search", "Bellman-Ford", "Bubble sort", "Breadth-first search"],
    "answer": 1,
    "explain": "Bellman-Ford relaxes every edge V-1 times rather than trusting a greedy finalize order, so it tolerates negative weights and can even flag a negative cycle. The cost is its slower O(V*E) running time."
  }
]
```