Мне нужна помощь в поиске всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе.
Я могу найти один из кратчайших путей с помощью BFS, но пока я не понимаю, как мне найти и распечатать их все.
Любое представление об алгоритме / псевдокоде, который я мог бы использовать?
В качестве предостережения помните, что может быть экспоненциально много кратчайших путей между двумя узлами в графе. Любой алгоритм для этого потенциально может занять экспоненциальное время.
Тем не менее, есть несколько относительно простых алгоритмов, которые могут найти все пути. Вот два.
При выполнении поиска в ширину по графу вы можете пометить каждый узел его расстоянием от начального узла. Начальный узел находится на расстоянии 0, а затем, когда новый узел обнаруживается впервые, его расстояние равно единице плюс расстояние узла, который его обнаружил. Итак, начните с запуска BFS по графу, записывая расстояния до каждого узла.
Получив это, вы можете найти кратчайший путь от источника до места назначения следующим образом. Начните с пункта назначения, который будет на некотором расстоянии d от начального узла. Теперь посмотрите на все узлы с ребрами, входящими в целевой узел. Кратчайший путь от источника до места назначения должен заканчиваться следом за ребром от узла на расстоянии d-1 до места назначения на расстоянии d. Итак, начиная с конечного узла, пройдите назад через некоторое ребро к любому желаемому узлу на расстоянии d-1. Оттуда идите к узлу на расстоянии d-2, к узлу на расстоянии d-3 и т. Д., Пока не вернетесь в начальный узел на расстоянии 0.
Эта процедура вернет вам один путь в обратном порядке, и вы можете перевернуть его в конце, чтобы получить общий путь.
Затем вы можете найти все пути от источника к месту назначения, выполнив поиск в глубину от конечного узла обратно к начальному узлу, в каждой точке пытаясь всеми возможными способами пройти назад от текущего узел к предыдущему узлу, расстояние которого ровно на единицу меньше расстояния текущего узла.
(Я лично считаю, что это самый простой и чистый способ найти все возможные пути, но это только мое мнение.)
Этот следующий алгоритм представляет собой модификацию BFS, которую вы можете использовать в качестве этапа предварительной обработки для ускорения генерации всех возможных путей. Помните, что при запуске BFS он движется наружу по слоям, получая единственный кратчайший путь ко всем узлам на расстоянии 0, затем на расстоянии 1, затем на расстоянии 2 и т. Д. Мотивирующая идея BFS заключается в том, что любой узел на расстоянии k + 1 от начальный узел должен быть соединен ребром с некоторым узлом на расстоянии k от начального узла. BFS обнаруживает этот узел на расстоянии k + 1, находя некоторый путь длины k к узлу на расстоянии k, а затем расширяя его на некоторое ребро.
Если ваша цель - найти все кратчайшие пути, вы можете изменить BFS, расширив каждый путь до узла на расстоянии k до всех узлов на расстоянии k + 1, на котором они подключаться к нему, а не выбирать одно ребро. Для этого измените BFS следующим образом: всякий раз, когда вы обрабатываете край, добавляя его конечную точку в очередь обработки, не отмечайте немедленно этот узел как выполненный. Вместо этого вставьте этот узел в очередь с пометкой, с какой стороны вы следовали, чтобы добраться до него. Это потенциально позволит вам вставить один и тот же узел в очередь несколько раз, если к нему подключено несколько узлов. Когда вы удаляете узел из очереди, вы отмечаете его как выполненное и больше никогда не вставляете его в очередь. Точно так же вместо хранения одного родительского указателя вы сохраните несколько родительских указателей, по одному для каждого узла, связанного с этим узлом.
Если вы сделаете эту модифицированную BFS, вы получите DAG, в котором каждый узел будет либо начальным узлом и не будет иметь исходящих ребер, либо будет находиться на расстоянии k + 1 от начального узла и будет иметь указатель на каждый узел расстояние k, к которому он подключен. Оттуда вы можете восстановить все кратчайшие пути от некоторого узла к начальному узлу, перечислив все возможные пути от выбранного вами узла обратно к начальному узлу в группе DAG. Это можно сделать рекурсивно:
Этот подход требует больше времени и места, чем тот, который указан выше, потому что многие пути, найденные таким образом, не будут двигаться в направлении узла назначения. Однако для этого требуется только модификация BFS, а не BFS с последующим обратным поиском.
Надеюсь это поможет!
@templatetypedef верен, но он забыл упомянуть о проверке расстояния, которая должна выполняться перед добавлением родительских ссылок в узел. Это означает, что 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 можно найти по следующей ссылке.
Я столкнулся с аналогичной проблемой при решении этой https://oj.leetcode.com/problems/word-ladder-ii/
Я пытался сначала найти кратчайшее расстояние с помощью BFS, скажем, самое короткое расстояние - d. Теперь примените DFS и в рекурсивном вызове DFS не выходите за пределы рекурсивного уровня d.
Однако это может закончиться исследованием всех путей, упомянутых @templatetypedef.
Сначала найдите расстояние до начала всех узлов с помощью поиска в ширину.
(если узлов много, вы можете использовать A * и останавливаться, когда в верхней части очереди будет distance-to-start > distance-to-start(end-node). Это даст вам все узлы, принадлежащие некоторому кратчайшему пути)
Затем просто вернитесь к конечному узлу. Каждый раз, когда узел соединяется с двумя (или более) узлами с меньшим начальным расстоянием, вы разветвляетесь на два (или более) пути.
templatetypedef ваш ответ был очень хорошим, большое вам спасибо (!!), но он упустил один момент:
Если у вас есть такой график:
A-B-C-E-F | | D------
Теперь представим, что мне нужен этот путь:
A -> E.
Он будет расширяться так:
A-> B -> D-> C -> F -> E.
The problem there is, that you will have F as a parent of E, but
A->B->D->F-Eis longer than
A->B->C->E.You will have to take of tracking the distances of parents you are so happily adding.
Шаг 1.Пройдите график от источника с помощью BFS и назначьте каждому узлу минимальное расстояние от источника.
Шаг 2: расстояние, назначенное целевому узлу, является самой короткой длиной
Шаг 3: Из источника выполните поиск DFS по всем путям, где минимальное расстояние увеличивается один за другим, пока не будет достигнут целевой узел или не будет достигнута самая короткая длина. Печатайте путь всякий раз, когда достигается целевой узел.
BFS останавливается, когда вы находите то, что хотите.
Вы должны изменить алгоритм, чтобы он продолжал выполнение после нахождения первого пути. (удалите оператор return и как-нибудь сохраните путь.
Вы можете завершить выполнение после проверки последнего узла уровня, который имеет конечные узлы кратчайших путей. (Все конечные узлы кратчайших путей находятся на одном уровне)
Также известен алгоритм, который находит все кратчайшие пути:
алгоритм Флойда – Уоршолла (имеет псевдокод)
