Какой алгоритм я могу использовать, чтобы найти ближайший к кратчайшему пути в графе?

Question

Я хочу найти следующий кратчайший путь между двумя вершинами в графе, и этот путь имеет положительную стоимость. Следующий кратчайший путь разрешен для совместного использования ребер кратчайшего пути. Какой алгоритм я могу использовать?

Answer 1

Используйте алгоритм K-кратчайшего пути, где k = 2, пример для примера:

Нахождение k кратчайших путей.Д. Эппштейн.35-й IEEE Symp.Основы Comp.Sci., Santa Fe, 1994, pp. 154-165.Tech.Отчет 94-26, ICS, UCI, 1994. SIAM J. Computing 28 (2): 652-673, 1998.

http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf

Answer 2

Я сомневаюсь, что это оптимально с точки зрения времени выполнения, но:

1. Используйте алгоритм Дейкстры на графе G, чтобы получить путь P
2. Для всех ребер E в пути P:
3. - Если G - E не подключен, переходите к следующему ребру (перейдите к 2)
4. - Используйте алгоритм Дейкстры на G - E, чтобы найти путь X_i
5. -Если длина текущего X_i короче, чем у всех остальных X_i, сохраните его
6. X_i в конце цикла for - это второй кратчайший путь

Второй кратчайший путь может 'не пройти через все ребра в P, но потенциально может пройти через все, кроме одного.Под «вторым кратчайшим» я предполагаю, что вы не используете ребра более одного раза, иначе второй кратчайший путь может содержать P.

Answer 3

Одним из способов является использование алгоритма Флойда-Варшалла для нахождения всех пар кратчайшего пути, а затем проверка всех промежуточных ребер - верный, но, возможно, не оптимальный способ - решить эту проблему. Вот отличное объяснение http://hatemabdelghani.wordpress.com/2009/07/04/second-shortest-path/

Answer 4

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

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

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

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

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

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

Answer 5

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

Напомним, что максимальный поток в сети между двумя узлами A и B дает вам количество непересекающихся по краю путей между этими двумя узлами.Также помните, что алгоритмы, такие как Edmonds-Karp , работают, посылая поток по кратчайшему пути на каждом шаге.

Таким образом, эта проблема имеет решение, только если максимальный поток между вашими узлами>>1, где каждое ребро имеет емкость 1. Если это так, найдите два увеличивающих пути, как описано в алгоритме Эдмондса-Карпа, и второй является вашим вторым кратчайшим.

См. эта проблема и это решение к нему (описание на китайском языке. Я не могу его перевести, и babelfish тоже не может этого сделать, но не примет это. Код легко выполнитьхотя) для примера.

Answer 6

Используйте алгоритм кратчайший путь , чтобы найти кратчайший путь, P.

Затем вы можете рассматривать эту проблему как проблему удовлетворения ограничения (где ограничение«кратчайший путь, который не является P»), и используйте алгоритм обратного отслеживания , чтобы найти кратчайший путь, который не является кратчайшим путем, который вы уже нашли.

Answer 7

Вы ищете 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]

Answer 8

Когда вы предпочитаете практическое решение академическому, вот оно.

Я решил эту проблему, установив штраф к краям кратчайшего пути и снова выполнив поиск.

Например, кратчайший путь имеет длину 1000, штраф составляет 10%, поэтому я ищу второй кратчайший путь с 1000 <= length <= 1100.</p>

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

Увеличение штрафа вынуждает алгоритм находить альтернативные маршруты, а уменьшение делает его совместным с допустимым.

Когда я нахожу 2-й кратчайший путь, я должен вычесть сумму штрафов по общим ребрам из вычисленной длины, чтобы получить реальную длину.

Для k-го кратчайшего пути я устанавливаю штраф для всех ребер, использованных в предыдущих k-1 кратчайших путях.