Dijkstra with Fibonacci Heap, in depth: decrease-key in O(1), the potential-function proof, and when it actually wins

What Dijkstra asks of its priority queue

Dijkstra keeps a tentative distance for every vertex it has reached and repeatedly settles the unsettled vertex with the smallest one. With non-negative weights, that distance can never improve later, so it is final. Settling u relaxes each edge u→v: if the path through u is shorter, lower v's distance. Over a graph with V reachable vertices and E edges, that is:

• V inserts, one the first time each vertex is reached;
• V extract-mins, one per settled vertex;
• up to E decrease-keys, one per improving relaxation.

E can approach V squared, so decrease-key is the hot operation. A binary heap charges O(log V) for everything, giving O((V + E) log V). Fredman and Tarjan designed the Fibonacci heap (1984, journal version 1987) so that insert and decrease-key cost O(1) amortized and extract-min costs O(log V) amortized. The total is O(E + V log V). For comparison-based Dijkstra that cannot be beaten if the vertices must come out in sorted order, since that sorts V numbers. Amortized bounds cap the total over any sequence of operations, not each call, and the total is all Dijkstra cares about.

The structure: lazy trees, a min pointer and marks

A Fibonacci heap is a set of heap-ordered trees (every key at least its parent's) whose roots form a circular doubly linked list. The heap keeps a pointer to the minimum root. Each node stores its key, parent, one child, left and right siblings (siblings also form a ring), its degree and one boolean, the mark.

The design is lazy. Insert adds a one-node tree to the root list and does nothing else. All tidying is postponed to extract-min, which must scan for a new minimum anyway. It links roots of equal degree until every root has a distinct degree, a pass called consolidation.

Decrease-key never sifts. If the lowered key breaks order with the parent, the node and its subtree are cut out and become a new root in O(1). Unlimited cutting would leave long, thin trees and break the logarithmic degree bound, so a non-root that loses one child is marked, and a marked node that loses a second child is cut too, possibly triggering its own parent: the cascading cut.

A complete implementation

The implementation below keeps nodes as objects so Dijkstra can hold a handle to each vertex's node and call decrease-key on it directly. Consolidation snapshots the root ring before linking, because linking mutates the ring while you iterate. That is the classic bug in hand-written versions.

class Node:
    __slots__ = ("key", "item", "parent", "child", "left", "right", "degree", "mark")

    def __init__(self, key, item):
        self.key, self.item = key, item
        self.parent = self.child = None
        self.left = self.right = self      # circular doubly linked list
        self.degree, self.mark = 0, False


class FibHeap:
    def __init__(self):
        self.min, self.n = None, 0

    def _splice(self, a, b):               # insert b's ring into a's ring
        a_right, b_left = a.right, b.left
        a.right, b.left = b, a
        a_right.left, b_left.right = b_left, a_right

    def _unlink(self, x):                   # remove x from its ring
        x.left.right, x.right.left = x.right, x.left
        x.left = x.right = x

    def insert(self, key, item):            # O(1): new single-node tree
        x = Node(key, item)
        if self.min is None:
            self.min = x
        else:
            self._splice(self.min, x)
            if key < self.min.key:
                self.min = x
        self.n += 1
        return x                            # handle for decrease_key

    def extract_min(self):                  # O(log n) amortized
        z = self.min
        if z is None:
            return None
        if z.child is not None:             # promote children to roots
            c = z.child
            for _ in range(z.degree):
                c.parent, c.mark = None, False
                c = c.right
            self._splice(z, z.child)
            z.child = None
        if z.right is z:
            self.min = None
        else:
            self.min = z.right
            self._unlink(z)
            self._consolidate()
        self.n -= 1
        return z

    def _consolidate(self):
        by_degree = {}
        roots, x = [], self.min             # snapshot: linking mutates the ring
        while True:
            roots.append(x)
            x = x.right
            if x is self.min:
                break
        for x in roots:
            d = x.degree
            while d in by_degree:
                y = by_degree.pop(d)
                if y.key < x.key:
                    x, y = y, x
                self._unlink(y)             # y becomes a child of x
                y.parent, y.mark = x, False
                if x.child is None:
                    x.child = y
                else:
                    self._splice(x.child, y)
                x.degree += 1
                d += 1
            by_degree[d] = x
        self.min = None
        for x in by_degree.values():
            if self.min is None or x.key < self.min.key:
                self.min = x

    def decrease_key(self, x, key):         # O(1) amortized
        assert key <= x.key
        x.key = key
        p = x.parent
        if p is not None and x.key < p.key:
            self._cut(x, p)
            self._cascading_cut(p)
        if x.key < self.min.key:
            self.min = x

    def _cut(self, x, p):
        if p.child is x:
            p.child = x.right if x.right is not x else None
        self._unlink(x)
        p.degree -= 1
        x.parent, x.mark = None, False
        self._splice(self.min, x)

    def _cascading_cut(self, y):
        while y.parent is not None:
            if not y.mark:                  # first child lost: remember it
                y.mark = True
                return
            p = y.parent                    # second child lost: cut y too
            self._cut(y, p)
            y = p

Dijkstra on top of it inserts a vertex the first time it is reached, not all vertices up front. That keeps the heap small on large graphs where most vertices are never touched.

def dijkstra(adj, source):
    """adj: {u: [(v, w), ...]} with w >= 0. Returns dist and parent maps."""
    heap, handle = FibHeap(), {}
    dist, parent = {source: 0}, {source: None}
    handle[source] = heap.insert(0, source)
    done = set()
    while heap.n:
        u = heap.extract_min().item
        done.add(u)
        del handle[u]
        for v, w in adj.get(u, ()):
            if v in done:
                continue
            nd = dist[u] + w
            if v not in dist:                       # first sighting: insert
                dist[v], parent[v] = nd, u
                handle[v] = heap.insert(nd, v)
            elif nd < dist[v]:                      # better path: decrease
                dist[v], parent[v] = nd, u
                heap.decrease_key(handle[v], nd)
    return dist, parent

Why the bounds hold

The analysis uses the potential function Φ = t + 2m, where t is the number of roots and m the number of marked nodes. The amortized cost of an operation is its actual cost plus the change in Φ. Since Φ starts at zero and never goes negative, the total amortized cost bounds the total actual cost.

• Insert does O(1) work and adds one root, so ΔΦ = +1. Amortized O(1).
• Decrease-key with c cascading cuts does O(c + 1) work. Each cut adds a root (+1 each). Every cascading cut unmarks a node (−2 each), and at most one node becomes newly marked (+2). So ΔΦ ≤ (c + 1) − 2c + 2 = 3 − c, and the amortized cost is O(c + 1) + 3 − c = O(1) once the potential is scaled to match the unit of work. Each cut is paid for by the mark it clears. This is why the mark costs 2 units: one pays for the cut, the other for the new root it creates.
• Extract-min promotes at most D(n) children, where D(n) is the maximum degree, then consolidates t + D(n) roots in O(t + D(n)) time. After consolidation at most D(n) + 1 roots remain, so Φ drops by about t, which cancels the t term. Amortized O(D(n)).

The remaining step is to show that D(n) = O(log n), and this is where the name comes from. Consider a node x and order its children by the time they were linked. When the i-th child was linked, x already had at least i − 1 children, and linking only joins equal degrees, so that child also had degree at least i − 1. Since then it has lost at most one child, because a second loss would have cut it, so its degree is still at least i − 2. By induction, a subtree whose root has degree k contains at least F(k + 2) nodes, where F is the Fibonacci sequence, and F(k + 2) ≥ φ^k with φ ≈ 1.618. So k ≤ log_φ n ≈ 1.44 log₂ n. The marks keep every tree bushy enough for that bound to hold.

Worked example: six vertices through the heap

Take vertices s, a, b, c, d, t and edges s→a 4, s→b 1, b→a 2, b→c 5, a→c 1, a→d 6, c→d 2, c→t 7, d→t 1.

Distances: s 0, b 1, a 3, c 4, d 6, t 7, via s→b→a→c→d→t. The work was 6 inserts, 6 extract-mins and 4 decrease-keys over 9 edges. Every extract-min left a single root, so nothing was linked, and every decrease-key hit a root, so nothing was cut. On path-like graphs the heap degenerates into a short list, and that is fine.

To see the machinery, insert p 10, q 20, r 30, u 40, v 50 and extract the minimum. Consolidation links equal-degree roots until one tree remains: q(r, u(v)), degree 2 with four nodes, within the Fibonacci bound F(4) = 3. Decrease v to 5: it is below its parent u, so v is cut to the root list and becomes the minimum, and u is marked. Decrease r to 25: still above q's 20, so no cut. If u lost another child, u would be cut too. On a random graph with 2,000 vertices and 40,000 edges, this code made about 1,200 cuts, roughly 100 of which triggered a cascading cut.

When it wins, and when it does not

Theory says the Fibonacci heap should win, but in practice it usually loses. Each node carries four pointers, and every operation chases them across memory, while a binary heap is a contiguous array with hot top levels in cache. Typical graphs are sparse (road networks have E around 2V to 3V), and there the constants swamp the asymptotic gap. On dense graphs, where the gap is real, an unsorted array with a linear minimum scan runs in O(V²) with no heap at all.

Research has moved on too. In 2024 Haeupler and co-authors showed that Dijkstra with a suitably designed heap is universally optimal, meaning optimal on every graph and not only in the worst case. In 2025 Duan and co-authors beat the sorting barrier for directed single-source shortest paths on sparse graphs. The Fibonacci heap bound is a classic, not a ceiling.

Failure modes

• Negative edges. Any heap gives wrong answers. Nothing crashes; vertices are settled too early. Validate weights or use Bellman-Ford.
• Mutating the root ring during consolidation. Walking x.right while linking skips or repeats roots. Snapshot first.
• Stale handles. Decrease-key on an extracted node corrupts the heap. Drop handles on settle.
• Uncleared marks. New roots and newly linked children must be unmarked, or spurious cascades void the bounds while answers stay correct.
• Silent pointer bugs. A broken sibling ring often still passes small tests. Compare against a heapq Dijkstra on hundreds of random graphs with self-loops, parallel and zero-weight edges, which is how this page's code was checked. In debug builds, also assert heap order, degree equal to the child-ring length, and correct parent pointers.

What to do next

1. Type in the FibHeap class and test it against a heapq Dijkstra on 600 random graphs before trusting it.
2. Write the invariant checker from the failure modes and run it after every operation in a debug build.
3. Time it against the heapq version on a sparse graph (E = 3V) and a dense one (E = V²/4) at V = 10,000, and record where, if anywhere, it wins.
4. Implement the O(V²) array Dijkstra and compare it on the dense graph too.
5. Replace the Fibonacci heap with a pairing heap behind the same insert, extract-min and decrease-key interface, and compare again.
6. Keep learning: Dijkstra as an engine with custom costs, the indexed priority queue, binary heap operations, Bellman-Ford for negative weights and A* pathfinding.