Поиск всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе

Мне нужна помощь в поиске всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе.

Я могу найти один из кратчайших путей с использованием BFS, но до сих пор я теряю то, как я мог найти и распечатать все из них.

Любая идея алгоритма/псевдокода, которую я мог бы использовать?

Ответы

Ответ 1

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

Тем не менее, существует относительно простая модификация BFS, которую вы можете использовать в качестве шага предварительной обработки для ускорения генерации всех возможных путей. Помните, что при запуске BFS он выходит наружу в "слоях", получая единственный кратчайший путь ко всем узлам на расстоянии 0, затем расстоянию 1, затем расстоянию 2 и т.д. Мотивационная идея BFS заключается в том, что любой node на расстоянии k + 1 с начала node должен быть соединен ребром с некоторым node на расстоянии k от начала node. BFS обнаруживает этот node на расстоянии k + 1, найдя некоторый путь длины k до a node на расстоянии k, а затем расширяя его на некоторое ребро.

Если ваша цель состоит в том, чтобы найти все кратчайшие пути, вы можете изменить BFS, расширив каждый путь до node на расстоянии k до всех узлов на расстоянии k + 1, к которому они подключаются, вместо того, чтобы выбирать один край, Для этого измените BFS следующим образом: всякий раз, когда вы обрабатываете ребро, добавляя свою конечную точку в очередь обработки, не сразу отмечайте, что node выполняется. Вместо этого вставьте этот node в очередь, аннотированную с каким краем вы следовали, чтобы добраться до него. Это потенциально позволит вам вставить один и тот же node в очередь несколько раз, если к нему привязаны несколько узлов. Когда вы удаляете node из очереди, вы отмечаете ее как выполняемую и никогда не вставляете ее в очередь. Аналогично, вместо хранения одного родительского указателя вы будете хранить несколько указателей родителя, по одному для каждого node, связанного с этим node.

Если вы выполните эту измененную BFS, вы получите DAG, где каждый node будет либо стартовым node, либо не будет иметь исходящих ребер, либо будет на расстоянии k + 1 от начала node и будет иметь указатель на каждый node расстояния k, к которому он подключен. Оттуда вы можете восстановить все кратчайшие пути от некоторого node до начала node, перечислив все возможные пути из вашего node выбора обратно в начало node в DAG. Это можно сделать рекурсивно:

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

Надеюсь, это поможет!

Ответ 2

@templatetypedef верен, но он забыл упомянуть о дистанционной проверке, которая должна быть выполнена до того, как любые родительские ссылки будут добавлены в node. Это означает, что se держит расстояние от источника в каждом из узлов и увеличивает на единицу расстояние для детей. Мы должны пропустить этот приращение и родительское добавление, если ребенок уже был посещен и имеет меньшее расстояние.

public void addParent(Node n) {
    // forbidding the parent it its level is equal to ours
    if (n.level == level) {
        return;
    }
    parents.add(n);

    level = n.level + 1;
}

Полную реализацию java можно найти по следующей ссылке.

http://ideone.com/UluCBb

Ответ 3

Сначала найдите расстояние до начала всех узлов, используя поиск по ширине.

(если есть много узлов, вы можете использовать A * и останавливаться, когда верхняя часть очереди имеет distance-to-start > distance-to-start(end-node). Это даст вам все узлы, которые принадлежат к кратчайшему пути)

Затем просто отступите от конца node. В любое время, когда node подключается к двум (или более) узлам с меньшим расстоянием до начала, вы отключаетесь на два (или более) пути.

Ответ 4

Я столкнулся с подобной проблемой при решении этого https://oj.leetcode.com/problems/word-ladder-ii/

То, как я пытался справиться, - это сначала найти кратчайшее расстояние, используя BFS, скажем, кратчайшее расстояние d. Теперь примените DFS и в рекурсивном вызове DFS не выходите за пределы рекурсивного уровня d.

Однако это может привести к изучению всех путей, упомянутых в @templatetypedef.

Ответ 5

templatetypedef ваш ответ был очень хорошим, спасибо вам за это (!!), но он пропустил одну точку:

Если у вас есть такой график:

A-B-C-E-F
  |     |
  D------

Теперь представьте себе, что я хочу этот путь:

A -> E.

Он будет расширяться следующим образом:

 A-> B -> D-> C -> F -> E.

Проблема в том, что у вас будет F как родитель E, но 

 A->B->D->F-E
больше, чем 

 A->B->C->E.
Вам нужно будет отслеживать расстояния родителей, с которыми вы так счастливо добавляете.

Ответ 6

BFS останавливается, когда вы находите то, что хотите.

Вам нужно изменить алгоритм, чтобы он продолжал выполнение, когда найден первый путь. (удалите оператор return и сохраните путь как-то.

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

Кроме того, существует известный алгоритм, который находит все кратчайшие пути:

алгоритм Флойда-Варшалла (у него есть псевдокод)

Джонсон алгоритм