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).

Answer 2

Let's suppose that your graph consists of vertices (Node) in your case you have 7 (0 ->6 ) and edges. These are represented by the following model :

Node model :

public class Vertex{
        final private String id;
        final private String name;


        public Vertex(String id, String name) {
                this.id = id;
                this.name = name;
        }
        public String getId() {
                return id;
        }

        public String getName() {
                return name;
        }

        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((id == null) ? 0 : id.hashCode());
                return result;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Vertex other = (Vertex) obj;
                if (id == null) {
                        if (other.id != null)
                                return false;
                } else if (!id.equals(other.id))
                        return false;
                return true;
        }

        @Override
        public String toString() {
                return name;
        }

}

And the edges will be present by this model : Edge

  public class Edge  {
        private final String id;
        private final Vertex source;
        private final Vertex destination;
        private final int weight;

        public Edge(String id, Vertex source, Vertex destination, int weight) {
                this.id = id;
                this.source = source;
                this.destination = destination;
                this.weight = weight;
        }

        public String getId() {
                return id;
        }
        public Vertex getDestination() {
                return destination;
        }

        public Vertex getSource() {
                return source;
        }
        public int getWeight() {
                return weight;
        }

        @Override
        public String toString() {
                return source + " " + destination;
        }


}

The graph (nodes + edges) will be present by this class : Graph

public class Graph {
        private final List<Vertex> vertexes;
        private final List<Edge> edges;

        public Graph(List<Vertex> vertexes, List<Edge> edges) {
                this.vertexes = vertexes;
                this.edges = edges;
        }

        public List<Vertex> getVertexes() {
                return vertexes;
        }

        public List<Edge> getEdges() {
                return edges;
        }



}

This is a simple implementation of Dijkstra’s algorithm. It does not use any performance optimization :

public class DijkstraAlgorithm {

        private final List<Vertex> nodes;
        private final List<Edge> edges;
        private Set<Vertex> settledNodes;
        private Set<Vertex> unSettledNodes;
        private Map<Vertex, Vertex> predecessors;
        private Map<Vertex, Integer> distance;

        public DijkstraAlgorithm(Graph graph) {
                // create a copy of the array so that we can operate on this array
                this.nodes = new ArrayList<Vertex>(graph.getVertexes());
                this.edges = new ArrayList<Edge>(graph.getEdges());
        }

        public void execute(Vertex source) {
                settledNodes = new HashSet<Vertex>();
                unSettledNodes = new HashSet<Vertex>();
                distance = new HashMap<Vertex, Integer>();
                predecessors = new HashMap<Vertex, Vertex>();
                distance.put(source, 0);
                unSettledNodes.add(source);
                while (unSettledNodes.size() > 0) {
                        Vertex node = getMinimum(unSettledNodes);
                        settledNodes.add(node);
                        unSettledNodes.remove(node);
                        findMinimalDistances(node);
                }
        }

        private void findMinimalDistances(Vertex node) {
                List<Vertex> adjacentNodes = getNeighbors(node);
                for (Vertex target : adjacentNodes) {
                        if (getShortestDistance(target) > getShortestDistance(node)
                                        + getDistance(node, target)) {
                                distance.put(target, getShortestDistance(node)
                                                + getDistance(node, target));
                                predecessors.put(target, node);
                                unSettledNodes.add(target);
                        }
                }

        }

        private int getDistance(Vertex node, Vertex target) {
                for (Edge edge : edges) {
                        if (edge.getSource().equals(node)
                                        && edge.getDestination().equals(target)) {
                                return edge.getWeight();
                        }
                }
                throw new RuntimeException("Should not happen");
        }

        private List<Vertex> getNeighbors(Vertex node) {
                List<Vertex> neighbors = new ArrayList<Vertex>();
                for (Edge edge : edges) {
                        if (edge.getSource().equals(node)
                                        && !isSettled(edge.getDestination())) {
                                neighbors.add(edge.getDestination());
                        }
                }
                return neighbors;
        }

        private Vertex getMinimum(Set<Vertex> vertexes) {
                Vertex minimum = null;
                for (Vertex vertex : vertexes) {
                        if (minimum == null) {
                                minimum = vertex;
                        } else {
                                if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
                                        minimum = vertex;
                                }
                        }
                }
                return minimum;
        }

        private boolean isSettled(Vertex vertex) {
                return settledNodes.contains(vertex);
        }

        private int getShortestDistance(Vertex destination) {
                Integer d = distance.get(destination);
                if (d == null) {
                        return Integer.MAX_VALUE;
                } else {
                        return d;
                }
        }

        /*
         * This method returns the path from the source to the selected target and
         * NULL if no path exists
         */
        public LinkedList<Vertex> getPath(Vertex target) {
                LinkedList<Vertex> path = new LinkedList<Vertex>();
                Vertex step = target;
                // check if a path exists
                if (predecessors.get(step) == null) {
                        return null;
                }
                path.add(step);
                while (predecessors.get(step) != null) {
                        step = predecessors.get(step);
                        path.add(step);
                }
                // Put it into the correct order
                Collections.reverse(path);
                return path;
        }

}

Then create a test class and add your graph values :

public class TestDijkstraAlgorithm {

        private List<Vertex> nodes;
        private List<Edge> edges;

        @Test
        public void testExcute() {
                nodes = new ArrayList<Vertex>();
                edges = new ArrayList<Edge>();
                for (int i = 0; i < 11; i++) {
                        Vertex location = new Vertex("Node_" + i, "Node_" + i);
                        nodes.add(location);
                }

                addLane("Edge_0", 0, 1, 5);
                addLane("Edge_1", 0, 2, 40);
                addLane("Edge_2", 0, 3, 21);
                addLane("Edge_3", 2, 3, 13);
                addLane("Edge_4", 2, 4, 19);
                addLane("Edge_5", 4, 5, 32);
                addLane("Edge_6", 3, 5, 41);
                addLane("Edge_7", 4, 6, 14);
                addLane("Edge_8", 5, 6, 8);


                // Lets check from location Loc_1 to Loc_10
                Graph graph = new Graph(nodes, edges);
                DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
                dijkstra.execute(nodes.get(0));
                LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10));

                assertNotNull(path);
                assertTrue(path.size() > 0);

                for (Vertex vertex : path) {
                        System.out.println(vertex);
                }

        }

        private void addLane(String laneId, int sourceLocNo, int destLocNo,
                        int duration) {
                Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), duration );
                edges.add(lane);
        }
}