Dijkstra算法。 最小堆作为最小优先级队列怎么理解?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (600)

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

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

为什么图应该是稀疏的?

以下是另一部分:

每次减少键操作都需要时间O(log V),而且目前最多仍有这类操作。

假设我的图形如下所示:

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

然后我需要在距离最近的节点上调用reduceKey来创建堆的新的最小值。 但我怎么知道它的指数在不断的时间?

节点

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;
    }

}
提问于
用户回答回答于

为什么图应该是稀疏的?

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

如果你的E比V小得多(如E << V² / logV),那么使用堆就变得更有效率了。

如果使用的是二进制堆,那么extractMin总是以O(log V)时间运行,并提供距离最近的节点(a.k.a.键)。

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

但是,在每个extractMininsertdecreaseKey之后,必须运行游泳或下沉以恢复堆状况,从而将最小距离的节点移动到顶部。 这需要O(log V)

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

用户回答回答于

假设你的图由顶点(节点)组成,在你的情况下,你有7(0->6)和边。以下模式代表了这些模式:

节点模型:

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;
        }

}

这种模型会显示边缘:边缘

  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;
        }


}

图(节点+边)将由这个类呈现:

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;
        }



}

这是Dijkstra算法的一个简单实现。它不使用任何性能优化:

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;
        }

}

然后创建一个测试类然后添加图形值:

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);
        }
}

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励