Which algorithm can I use to find the next to shortest path in a graph?

Предполагается, что вы можете повторно использовать ребра и узлы:

Прямое решение - сделать расширение алгоритма Джикстры.

• Вместо того, чтобы хранить для каждого узла наименьшую стоимость и его соответствующего родителя, сохраните две наименьшие затраты (и их соответствующих родителей).

• Для очереди приоритетов, для хранения узлов, сохраните пары (node, i), чтобы вы знали, использовать ли 1-й или 2-й путь во время распространения.

• Будьте внимательны во время фаз распространения, чтобы правильно обновлять значения нескольких путей.

(Я мог бы упустить некоторые важные детали, но основная идея здесь ...)

Вы ищете k маршрутизации по кратчайшему пути . По сути, запустите модифицированную Dijkstra, но вместо сохранения ребер в мини-куче сохраните все найденные пути.

Я предпочитаю рабочий код, так как дьявол всегда в деталях:

@SuppressWarnings("unchecked")
public static Iterable<Integer>[] kShortestPaths(EdgeWeightedDigraph g, int s, int t, int k) {
    if (k <= 0) throw new IllegalArgumentException("k must be positive");

    boolean[] visited = new boolean[g.V()];
    int[] count = new int[g.V()];
    MinPQ<Map.Entry<Map.Entry<Integer, Double>, Queue<Integer>>> heap = new MinPQ<>(
            comparingDouble(e -> e.getKey().getValue())
    );
    Queue<Integer>[] p = (Queue<Integer>[]) new Queue<?>[k];

    heap.insert(new SimpleImmutableEntry<>(new SimpleImmutableEntry<>(s, 0.0d), new Queue<>()));

    int i = 0;
    while (!heap.isEmpty()) {
        Map.Entry<Map.Entry<Integer, Double>, Queue<Integer>> node = heap.delMin();
        Integer u = node.getKey().getKey();
        if (count[u] >= k) break;

        Queue<Integer> pathU = node.getValue();
        visited[u] = true;
        pathU.enqueue(u);

        if (u == t) {
            p[i] = new Queue<>();
            for (int w : pathU) {
                p[i].enqueue(w);
            }
            i++;
        }

        if (count[u]++ <= k) {
            double costU = node.getKey().getValue();
            for (DirectedEdge e : g.adj(u)) {
                int v = e.to();
                if (!visited[v]) {
                    Queue<Integer> pathV = new Queue<>();
                    for (int w : pathU) {
                        pathV.enqueue(w);
                    }
                    heap.insert(new SimpleImmutableEntry<>(new SimpleImmutableEntry<>(v, e.weight() + costU), pathV));
                }
            }
        }
    }
    return p;
}

EdgeWeightedDigraph и MinPQ из https://github.com/kevin-wayne/algs4 .

k = 1, p = [0, 1, 2, 3]

k = 2, p = [0 , 4, 5, 3]