java - 第二最短/第 k 最短路径

Question

使用下面的代码，我试图找到第二条最短路径/第 k 条最短路径。

// Run Dijkstra's algorithm on given graph
    public static void shortestPath(GraphModel graph, int source, int destination, int numberOfVertices)
    {
        // create min heap and push source node having distance 0
        PriorityQueue<NodeModel> minHeap = new PriorityQueue<>((lhs, rhs) -> lhs.weight - rhs.weight);
        minHeap.add(new NodeModel(source, 0));

        // set infinite distance from source to v initially
        List<Integer> dist = new ArrayList<>(Collections.nCopies(numberOfVertices, Integer.MAX_VALUE));

        // distance from source to itself is zero
        dist.set(source, 0);

        // boolean array to track vertices for which minimum
        // cost is already found
        boolean[] done = new boolean[numberOfVertices];
        done[0] = true;

        // stores predecessor of a vertex (to print path)
        int prev[] = new int[numberOfVertices];
        prev[0] = -1;

        // run till minHeap is not empty
        while (!minHeap.isEmpty())
        {
            // Remove and return best vertex
            NodeModel node = minHeap.poll();
            node = minHeap.poll();
            // get vertex number
            int u = node.vertex;

            // do for each neighbor v of u
            for (EdgeModel edge: graph.adjList.get(u))
            {
                int v = edge.dest;
                int weight = edge.weight;
                // Relaxation step
                if (!done[v] && (dist.get(u) + weight) < dist.get(v))
                {
                    dist.set(v, dist.get(u) + weight);
                    prev[v] = u;
                    minHeap.add(new NodeModel(v, dist.get(v)));
                }
            }

            // marked vertex u as done so it will not get picked up again
            done[u] = true;
        }

这是图表。

    List<EdgeModel> edges = Arrays.asList(
            new EdgeModel(0, 1, 10), 
            new EdgeModel(0, 4, 3),
            new EdgeModel(1, 2, 5), 
            new EdgeModel(1, 4, 1),
            new EdgeModel(2, 3, 7), 
            new EdgeModel(2, 4, 8),
            new EdgeModel(3, 4, 2), 
            new EdgeModel(4, 1, 20)
    );

The shortest path from 0-4 is 3

The second shortest path from 0-4 is 11

Answer 1

你可以看看 Yen 的算法。该算法用于为单个源和单个目的地查找第 k 条最短路径(多条路径)。该算法假定您已使用 Djikstra 或任何其他算法找到最短路径。这是供您引用的链接:https://en.wikipedia.org/wiki/Yen%27s_algorithm