Dijkstra algorithm. Min heap as a min-priority queue

Question

I'm reading about Dijkstra's algorithm in CLRS, Third Edition (p. 662). Here is a part from the book I don't understand:

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.

Why should the graph be sparse?

---

Here is another part:

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

Suppose my graph looks like this:

I'd like to calculate the shortest path from 1 to 6 and use the min-heap approach. So first off, I add all my nodes to a min priority queue. After building a min heap, the min node is the source node (since its distance to itself is 0). I extract it and update distances of all its neighbors.

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?

Node

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

Why should the graph be sparse?

The running time of Dijkstra's algorithm depends on the combination of the underlying data structure and the graph shape (edges and vertices).

For example, using a linked list would require O(V²) time, i.e. it only depends on the number of vertices. Using a heap would require O((V + E) log V), i.e. it depends on both the number of vertices and the number of edges.

If your E is sufficiently smaller compared to V (as in E << V² / logV), then using heap becomes more efficient.

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?

If you're using a binary heap, then extractMin always runs in O(log V) time and gives you the node with the lowest distance (a.k.a. key).

For example, if you're implementing the binary min-heap as an array H, then the first element of the array H[1] (by convention we count from 1) will always be the element with the lowest distance, so finding it only takes O(1).

However, after each extractMin, insert or decreaseKey you have to run swim or sink to restore the heap condition, consequently moving the lowest-distance node to the top. This takes O(log V).

What you also want to do is maintain a mapping between keys in the heap and vertices, as mentioned in the book: "make sure that vertices and corresponding heap elements maintain handles to each other" (briefly discussed in section 6.5).