在Dijkstra算法中用什么数据类型作为队列？

Question

我正在尝试在Java中实现Dijkstra算法（自学）。我使用维基百科提供的伪代码（链接）。现在在算法的最后，我应该执行 decrease-key v in Q;。我猜我应该用BinaryHeap或类似的东西来实现Q？这里应该使用哪种正确的（内置）数据类型？

private void dijkstra(int source) {
        int[] dist = new int[this.adjacencyMatrix.length];
        int[] previous = new int[this.adjacencyMatrix.length];
        Queue<Integer> q = new LinkedList<Integer>();

        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            dist[i] = this.INFINITY;
            previous[i] = this.UNDEFINED;
            q.add(i);
        }

        dist[source] = 0;

        while(!q.isEmpty()) {
            // get node with smallest dist;
            int u = 0;
            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(dist[i] < dist[u])
                    u = i;
            }

            // break if dist == INFINITY
            if(dist[u] == this.INFINITY) break;

            // remove u from q
            q.remove(u);

            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(this.adjacencyMatrix[u][i] == 1) {
                    // in a unweighted graph, this.adjacencyMatrix[u][i] always == 1;
                    int alt = dist[u] + this.adjacencyMatrix[u][i]; 
                    if(alt < dist[i]) {
                        dist[i] = alt;
                        previous[i] = u;

                        // here's where I should "decrease the key"
                    }
                }
            }
        }
    }

- Dänu

---

你真的应该使用 q 来获取最小距离的节点，否则执行 decrease-key v in Q; 没有任何意义。 - Ishtar

Answer 1

最简单的方法是使用优先队列，不必关心之前添加到优先队列中的键。这意味着您将在队列中多次拥有每个节点，但这并不会对算法产生影响。如果您查看它，稍后将选择已被替换的节点的所有版本，此时最接近的距离已经确定。

来自维基百科的检查if alt < dist[v]: 是使其工作的关键。运行时间只会稍微降低一点，但如果需要非常快速的版本，则必须进一步优化。

注意：像任何优化一样，这个应该小心处理，可能会导致奇怪且难以找到的错误（例如请参见这里）。对于大多数情况，仅使用remove和re-insert即可，但我在这里提到的技巧可以在Dijkstra实现成为瓶颈时稍微加快代码速度。

最重要的是，在尝试此操作之前，请确保了解您的优先队列如何处理优先级。队列中的实际优先级不应更改，否则您可能会破坏队列的不变量，这意味着存储在队列中的项目可能无法再检索。例如，在Java中，优先级与对象一起存储，因此您需要使用额外的包装器：

这是行不通的：

import java.util.PriorityQueue;

// Store node information and priority together
class Node implements Comparable<Node> {
  public int prio;
  public Node(int prio) { this.prio = prio; }

  public int compareTo(Node n) {
     return Integer.compare(this.prio, n.prio);
  }
}

...
...
PriorityQueue<Node> q = new PriorityQueue<Node>();
n = new Node(10);
q.add(n)
...
// let's update the priority
n.prio = 0;
// re-add
q.add(n);
// q may be broken now

因为在n.prio=0时，您也会更改队列中对象的优先级。 然而，以下方法可以正常工作：

import java.util.PriorityQueue;

// Only node information
class Node {
  // Whatever you need for your graph
  public Node() {}
}

class PrioNode {
   public Node n;
   public int prio;
   public PrioNode(Node n, int prio) {
     this.n = n;
     this.prio = prio;
   }

   public int compareTo(PrioNode p) {
      return Integer.compare(this.prio, p.prio);
   }
}

...
...
PriorityQueue<PrioNode> q = new PriorityQueue<PrioNode>();
n = new Node();
q.add(new PrioNode(n,10));
...
// let's update the priority and re-add
q.add(new PrioNode(n,0));
// Everything is fine, because we have not changed the value
// in the queue.

- LiKao

---

很好的观察。这让我省去了自己写优先队列的麻烦。 - wcochran

@GiovanniBotta：和往常一样。当你遇到重复的队列时，当然要将它们移除。一旦所有的都被移除，算法就完成了。运行时间介于使用链表实现队列的朴素实现O（|V| ^ 2）和使用斐波那契堆O（|E| + |V| log |V|）之间，因为任何时候出现在堆中的总节点数（包括重复项）受|V|的限制。对于任何一个节点，如果是重复的，那么遇到这个节点只意味着可以丢弃它，这可以在O（1）内完成。 - LiKao

@LiKao，当你从PQ中取出一条边时，需要确保它与源点的距离是正确的，如果不正确则丢弃它？这很有道理。我想进行更彻底的运行时间分析以确定上限，但这听起来是合理的。 - Giovanni Botta

@GiovanniBotta：进行更彻底的分析应该不会太难。基本上，我们只需要查看使用链表或斐波那契堆实现Dijkstra算法的分析，并修改访问时间，添加重复O（1）复杂度即可。我已经有一段时间没有查看这些分析了，所以我不确定它们是如何工作的。 - LiKao

我不认为这是正确的。如果您更改现有节点的优先级，然后再将其插入到同一PriorityQueue中，那么它现在将存在于底层堆结构中两次，但其中一个位置将由于其当前优先级而是不正确的。这违反了堆的不变量，并可能导致未来的删除操作无法删除最低值。具体来说，优先级过低的节点可能会阻止节点在向上堆操作中上升到应该到达的高度。 - Adam Dingle

Answer 2

你可以使用TreeSet（在 C++ 中可以使用std::set）来实现Dijkstra算法的优先队列。 TreeSet 表示一个集合，但我们也允许描述集合中项目的排序。你需要将节点存储于集合中，并使用节点距离将节点排序。具有最小距离的节点将位于集合开头。

class Node {
    public int id;   // store unique id to distinguish elements in the set
    public int dist; // store distance estimates in the Node itself
    public int compareTo(Node other) {
        // TreeSet implements the Comparable interface.
        // We need tell Java how to compare two Nodes in the TreeSet.
        // For Dijstra, we want the node with the _smallest_ distance
        // to be at the front of the set.
        // If two nodes have same distance, choose node with smaller id
        if (this.dist == other.dist) {
            return Integer.compare(this.id, other.id);
        } else {
            return Integer.compare(this.dist, other.dist);
        }
    }
}
// ...
TreeSet<Node> nodes = new TreeSet<Node>();

extract-min 操作通过以下方式实现，并且最坏情况下需要 O(lgn) 的时间：

Node u = nodes.pollFirst();

通过减少键操作，我们删除旧键（旧距离估计）的节点，并添加具有较小键值（新的更好的距离估计）的新节点。这两个操作的最坏情况时间复杂度为O(lgn)。

nodes.remove(v);
v.dist = /* some smaller key */
nodes.add(v);

---

一些额外的说明：

• 以上实现非常简单，因为这两个操作在n的对数级别上，总体而言，运行时间将是O((n + e)lgn)。这被认为是Dijkstra基本实现的高效方法。请参阅CLRS book（ISBN：978-0-262-03384-8）第19章，以证明此复杂度。

• 尽管大多数教科书都会使用优先队列来实现Dijkstra、Prim、A*等算法，但不幸的是，Java和C++实际上都没有一个具有相同O(lgn)减少键操作的优先队列实现！

• PriorityQueue在Java中存在，但remove(Object o)方法不是对数级别的，因此您的减少键操作将是O(n)，而不是O(lgn)，并且（渐近地）您将获得较慢的Dikjstra！

• 要从零开始构建TreeSet（使用for循环），需要时间O(nlgn)，与从n个项初始化堆/优先队列的最坏情况时间O(n)相比稍慢。然而，Dijkstra的主循环需要时间O(nlgn + elgn)，这支配了这个初始化时间。因此，对于Dijkstra，初始化TreeSet不会导致任何显着的减速。

• 我们不能使用HashSet，因为我们关心键的顺序——我们想要能够首先取出最小的。这给了我们最佳距离估计的节点！

• Java中的TreeSet是使用红黑树实现的——一种自平衡二叉搜索树。这就是为什么这些操作具有对数级别的最坏情况时间。

• 您正在使用int来表示图形节点，这很好，但当您引入Node类时，您需要一种将两个实体相关联的方法。我建议在构建图形时构建一个HashMap<Integer，Node>——它将有助于跟踪哪个int对应于什么Node。

- James Lawson

---

除非每个路径都有唯一的距离，否则这种方法行不通。然而，我相信可以通过为每个节点分配一个唯一的ID，并在两个节点具有相同距离时，在compareTo()方法中考虑这个ID来解决问题。 - Craig P. Motlin

@CraigP.Motlin 你是对的，一个集合不能有重复元素。我会更正我的答案，使用节点 ID 而不是距离。 - James Lawson

在上面的代码中，你可以用 Integer.compare(this.id, other.id) 来代替 Integer.valueOf(this.id).compareTo(other.id)。 - Adam Dingle

Answer 3

建议使用的 PriorityQueue 没有提供 decrease-key 操作。不过，可以通过移除元素并将其重新插入以使用新键来模拟此操作。虽然这不会增加算法的渐近运行时间，但使用内置支持可以使其稍微快一些。

编辑：这确实会增加渐近运行时间，因为对于堆，decrease-key 预计为 O(log n)，而 remove(Object) 为 O(n)。似乎在 Java 中没有任何内置优先队列支持高效的 decrease-key。

- hammar

---

谢谢你提供这个。我想Apache Commons库里面包含了一个..不过，我打算自己实现一个.. :-) - Dänu

我们可以从优先队列中删除（O(log n)）个顶部元素，然后重新插入它（O(log n)）。通过这种方式，所有元素都会再次被重新组织。 <code> Object e = pq.poll(); pq.add(e);</code> - sattu

问题在于当优先级发生变化的不是顶部元素，而是中间某个位置的元素。 - Tim Cooper

Answer 4

根据维基百科文章，优先队列 是程序相关的内容。该文章建议经典实现现在是使用“由斐波那契堆实现的最小优先队列”。

- zellio

---

使用斐波那契堆总是更好吗？ - Amir Zadeh

绿色代码：学习Dijkstra可能有些过头，除非你也想学习斐波那契堆的实现。因此，在学习方面可能并不更好，但从实际性能来看似乎是更好的选择。 - zellio

我会尝试一下。实现斐波那契堆也应该很有趣 :-) - Dänu

如其他答案所提到的，Java的PriorityQueue不包括DecreaseKey方法，而这是必需的。因此，真正的答案是在Java中没有合适的内置类型可供使用。 - maayank

需要注意的是，斐波那契堆的常数相当差，因此在实践中，人们应该选择另一种类型的堆。 - Sebastian Paaske Tørholm

同意，在Java中，没有适用于Dijkstra算法的PQ。 - Giovanni Botta

Answer 5

是的，Java PriorityQueue 不提供最小堆的 decrease key 操作，因此移除操作的时间复杂度为 O(N)，但可以优化到 logN。

我已经实现了带有 decreaseKey 的最小堆（实际上是同时带有 increaseKey，但在这里只需要 decreaseKey）。实际数据结构是最小堆映射（HashMap 存储所有节点的索引，并通过当前顶点更新其邻居的最小路径值）。

我使用泛型实现了优化的解决方案，编码大约花费了我 3-4 小时（第一次尝试），时间复杂度为 O(logV.E)。

希望这能帮助到您！

 package algo;

 import java.util.*;

 public class Dijkstra {

/*
 *
 * @author nalin.sharma
 *
 */

/**
 *
 * Heap Map Data Structure
 * Heap stores the Nodes with their weight based on comparison on Node's weight
 * HashMap stores the Node and its index for O(1) look up of node in heap
 *
 *
 *
 *
 * Example -:
 *
 *                                   7
 *                         [2]----------------->[4]
 *                       ^  |                   ^ \
 *                     /   |                   |   \ 1
 *                 2 /    |                   |     v
 *                 /     |                   |       [6]
 *               /      | 1               2 |       ^
 *             /       |                   |      /
 *          [1]       |                   |     /
 *             \     |                   |    / 5
 *            4 \   |                   |   /
 *               v v                   |  /
 *                [3]---------------->[5]
 *                         3
 *
 *        Minimum distance from source 1
 *         v  | d[v] | path
 *         --- ------  ---------
 *         2 |  2  |  1,2
 *         3 |  3  |  1,2,3
 *         4 |  8  |  1,2,3,5,4
 *         5 |  6  |  1,2,3,5
 *         6 |  9  |  1,2,3,4,6
 *
 *
 *
 *     Below is the Implementation -:
 *
 */

static class HeapMap<T> {
    int size, ind = 0;
    NodeWeight<T> arr [];
    Map<T,Integer> map;

    /**
     *
     * @param t is the Node(1,2,3..or A,B,C.. )
     * @return the index of element in min heap
     */
    int index(T t) {
        return map.get(t);
    }

    /**
     *
     * @param index is the Node(1,2,3..or A,B,C.. )
     * @return Node and its Weight
     */
    NodeWeight<T> node(int index) {
        return arr[index];
    }

    /**
     *
     * @param <T> Node of type <T> and its weight
     */
    static class NodeWeight<T> {
        NodeWeight(T v, int w) {
            nodeVal = v;
            weight = w;
        }
        T nodeVal;
        int weight;
        List<T> path = new ArrayList<>();
    }

    public HeapMap(int s) {
        size = s;
        arr = new NodeWeight[size + 1];
        map = new HashMap<>();
    }

    private void updateIndex(T key, int newInd) {
        map.put(key, newInd);
    }

    private void shiftUp(int i) {
        while(i > 1) {
            int par = i / 2;
            NodeWeight<T> currNodeWeight = arr[i];
            NodeWeight<T> parentNodeWeight = arr[par];
            if(parentNodeWeight.weight > currNodeWeight.weight) {
                updateIndex(parentNodeWeight.nodeVal, i);
                updateIndex(currNodeWeight.nodeVal, par);
                swap(par,i);
                i = i/2;
            }
            else {
                break;
            }
        }
    }

    /**
     *
     * @param nodeVal
     * @param newWeight
     * Based on if the value introduced is higher or lower shift down or shift up operations are performed
     *
     */
    public void update(T nodeVal, int newWeight) {
        int i = ind;
        NodeWeight<T> nodeWeight = arr[map.get(nodeVal)];
        int oldWt = nodeWeight.weight;
        nodeWeight.weight = newWeight;
        if(oldWt < newWeight) {
            shiftDown(map.get(nodeVal));
        }
        else if(oldWt > newWeight) {
            shiftUp(map.get(nodeVal));
        }
    }

    /**
     *
     * @param nodeVal
     * @param wt
     *
     * Typical insertion in Min Heap and storing its element's indices in HashMap for fast lookup
     */
    public void insert(T nodeVal, int wt) {
        NodeWeight<T> nodeWt = new NodeWeight<>(nodeVal, wt);
        arr[++ind] = nodeWt;
        updateIndex(nodeVal, ind);
        shiftUp(ind);
    }

    private void swap(int i, int j) {
        NodeWeight<T> tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private void shiftDown(int i) {
        while(i <= ind) {
            int current = i;
            int lChild = i * 2;
            int rChild = i * 2 + 1;
            if(rChild <= ind) {
                int childInd = (arr[lChild].weight < arr[rChild].weight) ? lChild : rChild;
                if(arr[childInd].weight < arr[i].weight) {
                    updateIndex(arr[childInd].nodeVal, i);
                    updateIndex(arr[i].nodeVal, childInd);
                    swap(childInd, i);
                    i = childInd;
                }
            }
            else if(lChild <= ind && arr[lChild].weight < arr[i].weight) {
                updateIndex(arr[lChild].nodeVal, i);
                updateIndex(arr[i].nodeVal, lChild);
                swap(lChild, i);
                i = lChild;
            }
            if(current == i) {
                break;
            }
        }
    }

    /**
     *
     * @return
     *
     * Typical deletion in Min Heap and removing its element's indices in HashMap
     *
     */
    public NodeWeight<T> remove() {
        if(ind == 0) {
            return null;
        }
        map.remove(arr[1].nodeVal);
        NodeWeight<T> out = arr[1];
        out.path.add(arr[1].nodeVal);
        arr[1] = arr[ind];
        arr[ind--] = null;
        if(ind > 0) {
            updateIndex(arr[1].nodeVal, 1);
            shiftDown(1);
        }
        return out;
    }
}

/**
 *
 *  Graph representation -: It is an Map(T,Node<T>) of Map(T(neighbour), Integer(Edge's weight))
 *
 */
static class Graph<T> {

    void init(T... t) {
        for(T z: t) {
            nodes.put(z, new Node<>(z));
        }
    }

    public Graph(int s, T... t) {
        size = s;
        nodes = new LinkedHashMap<>(size);
        init(t);
    }

    /**
     *
     * Node class
     *
     */
    static class Node<T> {
        Node(T v) {
            val = v;
        }
        T val;
        //Set<Edge> edges = new HashSet<>();
        Map<T, Integer> edges = new HashMap<>();
    }

    /*static class Edge {
        Edge(int to, int w) {
            target = to;
            wt = w;
        }
        int target;
        int wt;
        }
    }*/

    int size;

    Map<T, Node<T>> nodes;

    void addEdge(T from, T to, int wt) {
        nodes.get(from).edges.put(to, wt);
    }
}

/**
 *
 * @param graph
 * @param from
 * @param heapMap
 * @param <T>
 *
 * Performs initialisation of all the nodes from the start vertex
 *
 */
    private static <T> void init(Graph<T> graph, T from, HeapMap<T> heapMap) {
    Graph.Node<T> fromNode = graph.nodes.get(from);
    graph.nodes.forEach((k,v)-> {
            if(from != k) {
                heapMap.insert(k, fromNode.edges.getOrDefault(k, Integer.MAX_VALUE));
            }
        });
    }


static class NodePathMinWeight<T> {
    NodePathMinWeight(T n, List<T> p, int c) {
        node = n;
        path = p;
        minCost= c;
    }
    T node;
    List<T> path;
    int minCost;
}

/**
 *
 * @param graph
 * @param from
 * @param <T>
 * @return
 *
 * Repeat the below process for all the vertices-:
 * Greedy way of picking the current shortest distance and updating its neighbors distance via this vertex
 *
 * Since Each Vertex V has E edges, the time Complexity is
 *
 * O(V.logV.E)
 * 1. selecting vertex with shortest distance from source in logV time -> O(logV) via Heap Map Data structure
 * 2. Visiting all E edges of this vertex and updating the path of its neighbors if found less via this this vertex. -> O(E)
 * 3. Doing operation step 1 and step 2 for all the vertices -> O(V)
 *
 */

    static <T> Map<T,NodePathMinWeight<T>> dijkstra(Graph<T> graph, T from) {
    Map<T,NodePathMinWeight<T>> output = new HashMap<>();
    HeapMap<T> heapMap = new HeapMap<>(graph.nodes.size());
    init(graph, from, heapMap);
    Set<T> isNotVisited = new HashSet<>();
    graph.nodes.forEach((k,v) -> isNotVisited.add(k));
    isNotVisited.remove(from);
    while(!isNotVisited.isEmpty()) {
        HeapMap.NodeWeight<T> currNodeWeight = heapMap.remove();
        output.put(currNodeWeight.nodeVal, new NodePathMinWeight<>(currNodeWeight.nodeVal, currNodeWeight.path, currNodeWeight.weight));
        //mark visited
        isNotVisited.remove(currNodeWeight.nodeVal);
        //neighbors
        Map<T, Integer> neighbors = graph.nodes.get(currNodeWeight.nodeVal).edges;
        neighbors.forEach((k,v) -> {
            int ind = heapMap.index(k);
            HeapMap.NodeWeight<T> neighbor = heapMap.node(ind);
            int neighborDist = neighbor.weight;
            int currentDistance = currNodeWeight.weight;
            if(currentDistance + v < neighborDist) {
                //update
                neighbor.path = new ArrayList<>(currNodeWeight.path);
                heapMap.update(neighbor.nodeVal, currentDistance + v);
            }
        });
    }
    return output;
}

public static void main(String[] args) {
    Graph<Integer> graph = new Graph<>(6,1,2,3,4,5,6);
    graph.addEdge(1,2,2);
    graph.addEdge(1,3,4);
    graph.addEdge(2,3,1);
    graph.addEdge(2,4,7);
    graph.addEdge(3,5,3);
    graph.addEdge(5,6,5);
    graph.addEdge(4,6,1);
    graph.addEdge(5,4,2);

    Integer source = 1;
    Map<Integer,NodePathMinWeight<Integer>> map = dijkstra(graph,source);
    map.forEach((k,v) -> {
        v.path.add(0,source);
        System.out.println("source vertex :["+source+"] to vertex :["+k+"] cost:"+v.minCost+" shortest path :"+v.path);
    });
}

}

输出-：

起点：[1] 终点：[2] 距离：2 最短路径：[1, 2]

起点：[1] 终点：[3] 距离：3 最短路径：[1, 2, 3]

起点：[1] 终点：[4] 距离：8 最短路径：[1, 2, 3, 5, 4]

起点：[1] 终点：[5] 距离：6 最短路径：[1, 2, 3, 5]

起点：[1] 终点：[6] 距离：9 最短路径：[1, 2, 3, 5, 4, 6]

- Nalin Sharma