每日算法 — 使用java实现斐波那契堆：Dijkstra算法的渐近最优优先队列

引言

在图论算法中，Dijkstra算法和Prim算法都依赖优先队列来高效选取当前距离/权值最小的顶点。普通二叉堆实现的优先队列支持插入和删除最小元素操作的时间复杂度均为O(log n)，这使得Dijkstra算法的总复杂度为O((V + E) log V)。

斐波那契堆（Fibonacci Heap）是一种更高级的数据结构，通过延迟合并（lazy consolidation）策略，将decrease-key操作的均摊时间复杂度降至O(1)。使用斐波那契堆后，Dijkstra算法的时间复杂度可优化至O(V log V + E)，对于稠密图尤为高效。

本文将用Java完整实现斐波那契堆，并展示其在Dijkstra最短路径算法中的应用。

核心原理

堆结构

斐波那契堆由一组最小堆有序的树组成，每棵树的根节点存储在循环双向链表中。每个节点包含：
– key：键值
– degree：子节点数量
– parent、child：父节点和任一子节点
– left、right：循环双向链表中的左右兄弟
– mark：是否失去过子节点（用于级联剪切）

关键操作复杂度

势函数分析

均摊分析使用势函数：$\Phi(H) = t(H) + 2m(H)$，其中t(H)为根列表中的树数量，m(H)为标记节点数量。

Java实现

import java.util.*;

/**
 * 斐波那契堆节点
 */
class FibNode {
    int vertex;           // 顶点编号
    double key;           // 键值（距离）
    int degree;           // 子节点数
    boolean mark;         // 是否失去过子节点
    FibNode parent;       // 父节点
    FibNode child;        // 任一子节点
    FibNode left;         // 左兄弟
    FibNode right;        // 右兄弟

    public FibNode(int vertex, double key) {
        this.vertex = vertex;
        this.key = key;
        this.degree = 0;
        this.mark = false;
        this.parent = null;
        this.child = null;
        // 初始化自环双向链表
        this.left = this;
        this.right = this;
    }
}

/**
 * 斐波那契堆实现
 */
class FibonacciHeap {
    private FibNode min;           // 最小节点
    private int n;                 // 节点总数
    private final Map<Integer, FibNode> nodeMap;  // 顶点 -> 节点映射

    public FibonacciHeap() {
        this.min = null;
        this.n = 0;
        this.nodeMap = new HashMap<>();
    }

    /**
     * 插入节点，均摊O(1)
     */
    public void insert(int vertex, double key) {
        FibNode node = new FibNode(vertex, key);
        nodeMap.put(vertex, node);
        n++;

        if (min == null) {
            min = node;
        } else {
            // 将node插入根列表
            insertIntoRootList(node);
            if (node.key < min.key) {
                min = node;
            }
        }
    }

    /**
     * 将节点插入根列表（循环双向链表）
     */
    private void insertIntoRootList(FibNode node) {
        if (min == null) {
            min = node;
            node.left = node;
            node.right = node;
            return;
        }
        node.left = min;
        node.right = min.right;
        min.right.left = node;
        min.right = node;
    }

    /**
     * 从链表中移除节点
     */
    private void removeFromList(FibNode node) {
        node.left.right = node.right;
        node.right.left = node.left;
    }

    /**
     * 获取最小键值，O(1)
     */
    public double minimum() {
        return min != null ? min.key : Double.POSITIVE_INFINITY;
    }

    /**
     * 提取最小节点，均摊O(log n)
     */
    public int extractMin() {
        FibNode z = min;
        if (z != null) {
            // 将所有子节点加入根列表
            if (z.child != null) {
                FibNode child = z.child;
                FibNode start = child;
                do {
                    FibNode next = child.right;
                    child.parent = null;
                    insertIntoRootList(child);
                    child = next;
                } while (child != start);
            }

            // 从根列表移除z
            removeFromList(z);
            if (z == z.right) {
                min = null;
            } else {
                min = z.right;
                consolidate();
            }
            n--;
            nodeMap.remove(z.vertex);
        }
        return z != null ? z.vertex : -1;
    }

    /**
     * 合并根列表中具有相同度数的树，均摊O(log n)
     */
    private void consolidate() {
        // 最大度数上界：D(n) <= floor(log_phi(n))，phi = (1+sqrt(5))/2
        int maxDegree = (int) (Math.log(n) / Math.log((1 + Math.sqrt(5)) / 2)) + 2;
        FibNode[] degreeTable = new FibNode[maxDegree + 1];

        // 收集所有根节点
        List<FibNode> roots = new ArrayList<>();
        if (min != null) {
            FibNode curr = min;
            do {
                roots.add(curr);
                curr = curr.right;
            } while (curr != min);
        }

        for (FibNode w : roots) {
            FibNode x = w;
            int d = x.degree;
            while (degreeTable[d] != null) {
                FibNode y = degreeTable[d];
                if (x.key > y.key) {
                    FibNode temp = x;
                    x = y;
                    y = temp;
                }
                link(y, x);
                degreeTable[d] = null;
                d++;
            }
            degreeTable[d] = x;
        }

        // 重建根列表并找到新的最小节点
        min = null;
        for (FibNode node : degreeTable) {
            if (node != null) {
                if (min == null) {
                    // 初始化只包含node的根列表
                    node.left = node;
                    node.right = node;
                    min = node;
                } else {
                    insertIntoRootList(node);
                    if (node.key < min.key) {
                        min = node;
                    }
                }
            }
        }
    }

    /**
     * 将y作为x的子节点，O(1)
     */
    private void link(FibNode y, FibNode x) {
        // 从根列表移除y
        removeFromList(y);
        // 使y成为x的子节点
        y.parent = x;
        y.mark = false;

        if (x.child == null) {
            x.child = y;
            y.left = y;
            y.right = y;
        } else {
            // 插入到x的子节点链表
            y.left = x.child;
            y.right = x.child.right;
            x.child.right.left = y;
            x.child.right = y;
        }
        x.degree++;
    }

    /**
     * 减小键值，均摊O(1)
     */
    public void decreaseKey(int vertex, double newKey) {
        FibNode x = nodeMap.get(vertex);
        if (x == null) return;
        if (newKey > x.key) {
            throw new IllegalArgumentException("New key is greater than current key");
        }
        x.key = newKey;
        FibNode y = x.parent;
        if (y != null && x.key < y.key) {
            cut(x, y);
            cascadingCut(y);
        }
        if (x.key < min.key) {
            min = x;
        }
    }

    /**
     * 剪切：将x从其父节点y处剪切，加入根列表
     */
    private void cut(FibNode x, FibNode y) {
        // 从y的子节点链表中移除x
        if (x.right == x) {
            y.child = null;
        } else {
            removeFromList(x);
            if (y.child == x) {
                y.child = x.right;
            }
        }
        y.degree--;

        // 将x加入根列表
        insertIntoRootList(x);
        x.parent = null;
        x.mark = false;
    }

    /**
     * 级联剪切
     */
    private void cascadingCut(FibNode y) {
        FibNode z = y.parent;
        if (z != null) {
            if (!y.mark) {
                y.mark = true;
            } else {
                cut(y, z);
                cascadingCut(z);
            }
        }
    }

    /**
     * 删除节点
     */
    public void delete(int vertex) {
        decreaseKey(vertex, Double.NEGATIVE_INFINITY);
        extractMin();
    }

    public boolean isEmpty() {
        return min == null;
    }

    public int size() {
        return n;
    }

    public boolean contains(int vertex) {
        return nodeMap.containsKey(vertex);
    }
}

/**
 * 图的邻接表表示
 */
class Graph {
    private final int V;
    private final List<Edge>[] adj;

    static class Edge {
        int to;
        double weight;
        Edge(int to, double weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    @SuppressWarnings("unchecked")
    public Graph(int V) {
        this.V = V;
        this.adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int from, int to, double weight) {
        adj[from].add(new Edge(to, weight));
    }

    public List<Edge> getNeighbors(int v) {
        return adj[v];
    }

    public int getV() { return V; }
}

/**
 * 使用斐波那契堆的Dijkstra算法
 */
class FibonacciDijkstra {
    /**
     * 计算单源最短路径
     * @return dist数组，dist[i]表示从source到i的最短距离
     */
    public static double[] shortestPath(Graph graph, int source) {
        int V = graph.getV();
        double[] dist = new double[V];
        int[] parent = new int[V];
        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        Arrays.fill(parent, -1);
        dist[source] = 0;

        FibonacciHeap heap = new FibonacciHeap();
        for (int v = 0; v < V; v++) {
            heap.insert(v, dist[v]);
        }

        while (!heap.isEmpty()) {
            int u = heap.extractMin();
            if (dist[u] == Double.POSITIVE_INFINITY) continue;

            for (Graph.Edge edge : graph.getNeighbors(u)) {
                int v = edge.to;
                double weight = edge.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                    if (heap.contains(v)) {
                        heap.decreaseKey(v, dist[v]);
                    }
                }
            }
        }

        return dist;
    }

    /**
     * 对比版本：使用普通优先队列（二叉堆模拟）
     */
    public static double[] shortestPathBinaryHeap(Graph graph, int source) {
        int V = graph.getV();
        double[] dist = new double[V];
        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        dist[source] = 0;

        PriorityQueue<NodeDist> pq = new PriorityQueue<>(Comparator.comparingDouble(nd -> nd.dist));
        pq.offer(new NodeDist(source, 0));

        while (!pq.isEmpty()) {
            NodeDist nd = pq.poll();
            int u = nd.node;
            if (nd.dist > dist[u]) continue;

            for (Graph.Edge edge : graph.getNeighbors(u)) {
                int v = edge.to;
                double weight = edge.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new NodeDist(v, dist[v]));
                }
            }
        }
        return dist;
    }

    static class NodeDist {
        int node;
        double dist;
        NodeDist(int node, double dist) {
            this.node = node;
            this.dist = dist;
        }
    }
}

/**
 * 性能测试与演示
 */
public class FibonacciHeapDemo {
    public static void main(String[] args) {
        // 基础功能测试
        System.out.println("=== 斐波那契堆基础测试 ===");
        FibonacciHeap heap = new FibonacciHeap();
        heap.insert(1, 5.0);
        heap.insert(2, 3.0);
        heap.insert(3, 8.0);
        heap.insert(4, 1.0);
        heap.insert(5, 7.0);

        System.out.println("最小值: " + heap.minimum());
        heap.decreaseKey(3, 0.5);
        System.out.println("decreaseKey(3, 0.5)后最小值: " + heap.minimum());

        System.out.print("extractMin顺序: ");
        while (!heap.isEmpty()) {
            System.out.print(heap.extractMin() + " ");
        }
        System.out.println();

        // Dijkstra算法演示
        System.out.println("\n=== Dijkstra最短路径演示 ===");
        Graph graph = new Graph(6);
        graph.addEdge(0, 1, 7);
        graph.addEdge(0, 2, 9);
        graph.addEdge(0, 5, 14);
        graph.addEdge(1, 2, 10);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 11);
        graph.addEdge(2, 5, 2);
        graph.addEdge(3, 4, 6);
        graph.addEdge(4, 5, 9);

        double[] dist = FibonacciDijkstra.shortestPath(graph, 0);
        System.out.println("从顶点0出发的最短距离:");
        for (int i = 0; i < dist.length; i++) {
            System.out.printf("  到顶点%d: %.1f%n", i, dist[i]);
        }

        // 性能对比
        System.out.println("\n=== 性能对比测试 ===");
        int[] sizes = {1000, 5000, 10000};
        for (int V : sizes) {
            Graph g = generateRandomGraph(V, V * 5);
            long start = System.nanoTime();
            FibonacciDijkstra.shortestPath(g, 0);
            long fibTime = System.nanoTime() - start;

            start = System.nanoTime();
            FibonacciDijkstra.shortestPathBinaryHeap(g, 0);
            long binTime = System.nanoTime() - start;

            System.out.printf("V=%d, E=%d: FibonacciHeap=%.2fms, BinaryHeap=%.2fms%n",
                    V, V * 5, fibTime / 1e6, binTime / 1e6);
        }
    }

    static Graph generateRandomGraph(int V, int E) {
        Graph g = new Graph(V);
        Random rand = new Random(42);
        for (int i = 0; i < E; i++) {
            int from = rand.nextInt(V);
            int to = rand.nextInt(V);
            if (from != to) {
                g.addEdge(from, to, rand.nextDouble() * 100);
            }
        }
        return g;
    }
}

算法分析

均摊分析要点

decrease-key的O(1)均摊复杂度源于：
1. 每次decrease-key最多引发一次cut操作（实际代价O(1)）
2. 级联剪切时，每两次标记节点的剪切才能清除一次标记
3. 势函数变化补偿了实际代价

extract-min的O(log n)均摊复杂度源于：
1. 合并操作使根列表中不存在两棵度数相同的树
2. 度数上限由斐波那契数列性质决定：$D_{max} = O(\log n)$
3. 势函数从t(H)降至O(log n)，支付了合并的实际代价

与二叉堆的对比

扩展思考

1. 严格斐波那契堆：通过更精细的势函数分析，可实现所有操作的严格最坏情况复杂度保证。
2. 配对堆：实践中常数因子更优的替代方案，decrease-key的均摊复杂度猜想为O(1)。
3. 热队列优化：在Dijkstra中结合桶结构（Dial算法），对整数权重可达O(V + E + C)。

总结

斐波那契堆通过延迟合并策略和级联剪切机制，在理论上为Dijkstra和Prim算法提供了最优的渐近时间复杂度。虽然在实际应用中由于常数因子较大，二叉堆或配对堆往往更具竞争力，但理解斐波那契堆的设计思想对于掌握高级数据结构和均摊分析技术至关重要。