java - 如何在Java中实现Dijkstra算法来寻找最短路径

Question

我完全不知道该怎么做。我正在尝试使用维基百科上关于 Dijkstra 的优先级队列的伪代码进行编码，但我很难进行调整以适应我需要找到的内容。到目前为止，这是我的(不完整的)代码，非常感谢任何帮助。

public int doDijkstras (String startVertexName, String endVertexName, ArrayList< String > shortestPath) {
        PriorityQueue<QEntry> q = new PriorityQueue<QEntry>();
        int cost = 0;
        int newCost;
        QEntry pred = null;
        for (String s : this.getVertices()) {
            if (!s.equals(startVertexName)) {
                cost = Integer.MAX_VALUE;
                pred = null;
            }
            q.add(new QEntry(s, cost, pred, adjacencyMap.get(s)));
        }

        while (!q.isEmpty()) {
            QEntry curr = getMin(q);
            for (String s : curr.adj.keySet()) {
                newCost = curr.cost + this.getCost(curr.name, s);
                QEntry v = this.getVert(q, s);
                if (newCost < v.cost) {
                    v.cost = newCost;
                    v.pred = curr;
                    if (!q.contains(curr)) {
                        q.add(curr);
                    }
                }
            }
        }
    }

    private QEntry getMin(PriorityQueue<QEntry> q) {
        QEntry min = q.peek();
        for (QEntry temp : q) {
            if (min.cost > temp.cost) {
                min = temp;
            }
        }
        return min;
    }

    private QEntry getVert(PriorityQueue<QEntry> q, String s) {
        for (QEntry temp : q) {
            if (temp.name.equals(s)) {
                return temp;
            }
        }
        return null;
    }

    class QEntry {
        String name;
        int cost;
        QEntry pred;
        TreeMap<String, Integer> adj;

        public QEntry(String name, int cost, QEntry pred, TreeMap<String, Integer> adj) {
            this.name = name;
            this.cost = cost;
            this.adj = adj;
            this.pred = pred;
        }
    }

Answer 1

您忽略了算法的一个重要部分:何时停止。

维基百科上的伪代码是 Dijkstra 算法的变体，该算法计算从起始节点到与其连接的每个节点的最短路径。紧随大伪代码块之后的注释解释了如何修改算法以仅查找到特定目标的路径，之后是一个较短的 block ，解释如何提取路径。

但是，在英语中，当您处理优先级队列时，您需要注意目标元素是否被选中。当(如果有)它出现时，您知道没有比将成本记录在目标队列条目中并由该条目及其前驱链表示(以相反顺序)的路径更短的路径了。您可以通过遍历前趋链来填充路径列表，并返回目标队列条目中记录的值。

但是请注意，在您的代码中，如果起始顶点和目标顶点在图中未连接(包括目标根本不在图中)，您最终将耗尽队列并退出while 循环的底部，但从未达到目标。您必须决定如何处理路径列表以及在这种情况下返回什么。

另请注意，您的代码似乎存在多个错误，其中:

• 如果起始顶点名称不是 this.getVertices() 迭代顺序中的第一个，则其队列条目不会以成本 0 初始化，并且不太可能从队列中选择的第一个元素。
• 如果指定的起始顶点根本不在图中，那么您的代码将运行，并且可能会发出一条路径，但在这种情况下其输出是伪造的。
• 您的队列元素(类型QEntry)没有自然顺序；要创建其元素具有此类类型的 PriorityQueue，您必须提供一个定义其相对优先级的 Comparator。
• 您正在将优先级队列用作普通列表。这本身不会使您的代码产生错误的结果，但它确实会增加其渐近复杂性。
• 但是请注意，如果您使用标准 PriorityQueue 作为优先级队列，则绝不能以可能改变排队对象顺序的方式修改排队对象相对于任何其他排队对象；相反，首先将其从队列中删除，修改它，然后再次将其入队。