Dijkstra算法.最小堆作为最小优先级队列

Question

我正在阅读CLRS第三版中的 Dijkstra算法(第662页).这是我不明白的书中的一部分:

如果图形足够稀疏 - 特别是E = o(V^2/lg V)- 我们可以通过使用二进制最小堆实现最小优先级队列来改进算法.

图为什么要稀疏？

---

这是另一部分:

每个DECREASE-KEY操作都需要时间O(log V),并且最多仍然有E这样的操作.

假设我的图形如下所示:

我想计算从1到6的最短路径并使用最小堆方法.首先,我将所有节点添加到最小优先级队列.构建最小堆后,min节点是源节点(因为它与自身的距离为0).我提取它并更新其所有邻居的距离.

然后我需要调用decreaseKey距离最小的节点来创建一个新的最小堆.但是如何在恒定时间内知道它的指数呢？

节点

private static class Node implements Comparable<Node> {

    final int key;
    int distance = Integer.MAX_VALUE;
    Node prev = null;

    public Node(int key) {
        this.key = key;
    }

    @Override
    public int compareTo(Node o) {
        if (distance < o.distance) {
            return -1;
        } else if (distance > o.distance) {
            return 1;
        } else {
            return 0;
        }
    }

    @Override
    public String toString() {
        return "key=" + key + " distance=" + distance;
    }

    @Override
    public int hashCode() {
        return key;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof Node)) {
            return false;
        }
        Node other = (Node) obj;
        return key == other.key;
    }
}

MinPriorityQueue

public static class MinPriorityQueue {

    private Node[] array;
    private int heapSize;

    public MinPriorityQueue(Node[] array) {
        this.array = array;
        this.heapSize = this.array.length;
    }

    public Node extractMin() {
        Node temp = array[0];
        swap(0, heapSize - 1, array);
        heapSize--;
        sink(0);
        return temp;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public void buildMinHeap() {
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            sink(i);
        }
    }

    public void decreaseKey(int index, Node key) {
        if (key.compareTo(array[index]) >= 0) {
            throw new IllegalArgumentException("the new key must be greater than the current key");
        }
        array[index] = key;
        while (index > 0 && array[index].compareTo(array[parentIndex(index)]) < 0) {
            swap(index, parentIndex(index), array);
            index = parentIndex(index);
        }
    }

    private int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private int left(int index) {
        return 2 * index + 1;
    }

    private int right(int index) {
        return 2 * index + 2;
    }

    private void sink(int index) {
        int smallestIndex = index;
        int left = left(index);
        int right = right(index);
        if (left < heapSize && array[left].compareTo(array[smallestIndex]) < 0) {
            smallestIndex = left;
        }
        if (right < heapSize && array[right].compareTo(array[smallestIndex]) < 0) {
            smallestIndex = right;
        }
        if (index != smallestIndex) {
            swap(smallestIndex, index, array);
            sink(smallestIndex);
        }
    }

    public Node min() {
        return array[0];
    }

    private void swap(int i, int j, Node[] array) {
        Node temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

Answer 1

图为什么要稀疏？

Dijkstra算法的运行时间取决于底层数据结构和图形(边和顶点)的组合.

例如,使用链表需要O(V²)时间,即它仅取决于顶点的数量.使用堆将需要O((V + E) log V),即它取决于顶点的数量和边的数量.

如果你的E比V(如在E << V² / logV)中足够小,那么使用堆会变得更有效率.

然后我需要调用decreaseKey距离最小的节点来创建一个新的最小堆.但是如何在恒定时间内知道它的指数呢？

如果您正在使用二进制堆,那么extractMin总是及时运行O(log V)并为您提供距离最短的节点(也称为密钥).

例如,如果您将二进制最小堆实现为数组H,那么数组的第一个元素H[1](按惯例我们计算1)将始终是具有最低距离的元素,因此只需要查找它O(1).

但是,在每次之后extractMin,insert或者decreaseKey您必须运行swim或sink恢复堆条件,从而将最低距离节点移动到顶部.这需要O(log V).

您还要做的是维护堆中的键和顶点之间的映射,如书中所述:"确保顶点和相应的堆元素保持彼此的句柄"(在6.5节中简要讨论).