heap - 迪杰斯特拉算法。最小堆作为最小优先级队列

Question

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

If the graph is sufficiently sparse — in particular, E = o(V^2/lg V) — we can improve the algorithm by implementing the min-priority queue with a binary min-heap.

为什么图形应该是稀疏的？

这是另一部分:

Each DECREASE-KEY operation takes time O(log V), and there are still at most E such operations.

假设我的图表如下所示:



我想计算从 1 到 6 的最短路径并使用最小堆方法。所以首先，我将所有节点添加到最小优先级队列中。建立最小堆后，最小节点就是源节点(因为它与自身的距离为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;
    }
}

最小优先级队列

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

Why should the graph be sparse?

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

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

如果您的 E 与 V 相比​​足够小(如 E << V² / logV 中)，那么使用堆会变得更有效。

Then I need to call decreaseKey on the node with the lowest distance to make a new minimum of the heap. But how do I know its index in constant time?

如果您使用的是二进制堆，那么 extractMin总是在 O(log V) 中运行时间并为您提供距离最短的节点(也称为键)。

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

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

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