使用Dijkstra的多个最短路径

Question

我目前使用Dijkstra算法寻找最短路径。这个算法给出的是最佳最短路径但我想要两条或两条以上的路径。我怎样才能做到这一点呢?

算法如下:

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

有Yen 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/shortestpaths

希望有帮助