Мне нужна помощь в поиске всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе.
Я могу найти один из кратчайших путей с использованием BFS, но до сих пор я теряю то, как я мог найти и распечатать все из них.
Любая идея алгоритма/псевдокода, которую я мог бы использовать?
Как предостережение, помните, что может быть экспоненциально много кратчайших путей между двумя узлами в графе. Любой алгоритм для этого потенциально займет экспоненциальное время.
Тем не менее, существует относительно простая модификация 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. Это можно сделать рекурсивно:
Надеюсь, это поможет!
@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 можно найти по следующей ссылке.
Сначала найдите расстояние до начала всех узлов, используя поиск по ширине.
(если есть много узлов, вы можете использовать A * и останавливаться, когда верхняя часть очереди имеет distance-to-start > distance-to-start(end-node). Это даст вам все узлы, которые принадлежат к кратчайшему пути)
Затем просто отступите от конца node. В любое время, когда node подключается к двум (или более) узлам с меньшим расстоянием до начала, вы отключаетесь на два (или более) пути.
Я столкнулся с подобной проблемой при решении этого https://oj.leetcode.com/problems/word-ladder-ii/
То, как я пытался справиться, - это сначала найти кратчайшее расстояние, используя BFS, скажем, кратчайшее расстояние d. Теперь примените DFS и в рекурсивном вызове DFS не выходите за пределы рекурсивного уровня d.
Однако это может привести к изучению всех путей, упомянутых в @templatetypedef.
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.Вам нужно будет отслеживать расстояния родителей, с которыми вы так счастливо добавляете.
BFS останавливается, когда вы находите то, что хотите.
Вам нужно изменить алгоритм, чтобы он продолжал выполнение, когда найден первый путь. (удалите оператор return и сохраните путь как-то.
Вы можете завершить выполнение после проверки последнего node уровня с конечными узлами кратчайших путей. (Все конечные узлы кратчайших путей находятся на одном уровне)
Кроме того, существует известный алгоритм, который находит все кратчайшие пути:
алгоритм Флойда-Варшалла (у него есть псевдокод)
как насчет этого: я нашел его в Интернете