java - 使用 Dijkstra 的多条最短路径

Question

我目前正在使用 Dijkstra 算法来查找最短路径。这个算法给了我最好的最短路径，但我想有 2 条或更多路径。我怎样才能做到这一点？

算法如下：

public class Dijkstra
{
    public static void computePaths(Vertex source)
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies)
            {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
        if (distanceThroughU < v.minDistance) {
            vertexQueue.remove(v);

            v.minDistance = distanceThroughU ;
            v.previous = u;
            vertexQueue.add(v);
        }
            }
        }
    }

Answer 1

有日元 top K 最短路径算法，它使用 Dijkstra 计算最佳路径，然后使用 Dijkstra 计算第二个最佳路径等。

我在这里找到了一个 Java 实现：https ://github.com/yan-qi/k-shortest-paths-java-version/tree/master/src/main/java/edu/asu/emit/algorithm/graph /最短路径

希望有帮助