Нахождение всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе
Мне нужна помощь в поиске всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе.
Я могу найти один из самых коротких путей, используя BFS, но до сих пор я теряюсь в том, как я могу найти и распечатать все из них.
Любая идея алгоритма / псевдокода я мог бы использовать?
9 ответов
В качестве предупреждения, помните, что может быть экспоненциально много кратчайших путей между двумя узлами в графе. Любой алгоритм для этого может занять экспоненциальное время.
Тем не менее, существует относительно простая модификация BFS, которую можно использовать в качестве шага предварительной обработки для ускорения генерации всех возможных путей. Помните, что во время работы BFS она продолжается в "слоях", получая один кратчайший путь ко всем узлам на расстоянии 0, затем на расстоянии 1, затем на расстоянии 2 и т. Д. Мотивирующая идея, лежащая в основе BFS, заключается в том, что любой узел на расстоянии k + 1 от начального узла должен быть соединен ребром с некоторым узлом на расстоянии k от начального узла. BFS обнаруживает этот узел на расстоянии k + 1, находя некоторый путь длины k до узла на расстоянии k, а затем расширяет его на некоторое ребро.
Если ваша цель - найти все кратчайшие пути, то вы можете изменить BFS, расширив каждый путь до узла на расстоянии k до всех узлов на расстоянии k + 1, к которым они подключаются, вместо того, чтобы выбирать один край. Чтобы сделать это, измените BFS следующим образом: всякий раз, когда вы обрабатываете ребро, добавляя его конечную точку в очередь обработки, не сразу помечайте этот узел как выполненный. Вместо этого вставьте этот узел в очередь, помеченную тем, по какому краю вы следовали, чтобы добраться до него. Это потенциально позволит вам вставить один и тот же узел в очередь несколько раз, если есть несколько узлов, которые ссылаются на него. Когда вы удаляете узел из очереди, вы помечаете его как выполненный и больше никогда не вставляете его в очередь. Аналогично, вместо хранения одного родительского указателя, вы будете хранить несколько родительских указателей, по одному для каждого узла, который связан с этим узлом.
Если вы сделаете эту модифицированную BFS, вы получите группу DAG, в которой каждый узел будет либо начальным узлом и не будет иметь исходящих ребер, либо будет находиться на расстоянии k + 1 от начального узла и будет иметь указатель на каждый узел расстояние к которому он подключен. Оттуда вы можете восстановить все кратчайшие пути от некоторого узла к начальному узлу, перечислив все возможные пути от выбранного узла обратно к начальному узлу в группе обеспечения доступности баз данных. Это можно сделать рекурсивно:
- Существует только один путь от начального узла к себе, а именно пустой путь.
- Для любого другого узла пути можно найти, следуя каждому исходящему ребру, а затем рекурсивно расширяя эти пути, чтобы получить путь обратно к начальному узлу.
Надеюсь это поможет!
@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 ваш ответ был очень хорош, большое спасибо за это (!!), но он упустил один момент:
Если у вас есть такой график:
ABCEF | | D------
Теперь давайте представим, что я хочу этот путь:
A -> E.
Это будет расширяться так:
A-> B -> D-> C -> F -> E.
Проблема в том, что вы будете иметь F в качестве родителя E, но
A-> B-> D-> FEдлиннее чем
A-> B-> C-> Е.Вам придется отслеживать расстояния между родителями, которых вы так радостно добавляете.
Последовательность преобразования слова beginWord в слово endWord с помощью словаря wordList представляет собой последовательность слов beginWord.
-> s1 -> s2 -> ... -> skтак что:
Каждая соседняя пара слов отличается на одну букву. Каждый си для
1 <= i <= kнаходится в списке слов. Обратите внимание, что beginWord не обязательно должен находиться в списке слов. sk == endWord Даны два слова, beginWord и endWord, и словарь wordList, возвращает все кратчайшие последовательности преобразования из beginWord в endWord или пустой список, если такой последовательности не существует. Каждая последовательность должна быть возвращена в виде списка слов
[beginWord, s1, s2, ..., sk].
Пример 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
Пример 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Объяснение: EndWord "cog" отсутствует в списке слов, поэтому не существует действительной последовательности преобразования.
https://leetcode.com/problems/word-ladder-ii
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
if (wordList == null) {
return result;
}
Set<String> dicts = new HashSet<>(wordList);
if (!dicts.contains(endWord)) {
return result;
}
Set<String> start = new HashSet<>();
Set<String> end = new HashSet<>();
Map<String, List<String>> map = new HashMap<>();
start.add(beginWord);
end.add(endWord);
bfs(map, start, end, dicts, false);
List<String> subList = new ArrayList<>();
subList.add(beginWord);
dfs(map, result, subList, beginWord, endWord);
return result;
}
private void bfs(Map<String, List<String>> map, Set<String> start, Set<String> end, Set<String> dicts, boolean reverse) {
// Processed all the word in start
if (start.size() == 0) {
return;
}
dicts.removeAll(start);
Set<String> tmp = new HashSet<>();
boolean finish = false;
for (String str : start) {
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char old = chars[i];
for (char n = 'a' ; n <='z'; n++) {
if(old == n) {
continue;
}
chars[i] = n;
String candidate = new String(chars);
if (!dicts.contains(candidate)) {
continue;
}
if (end.contains(candidate)) {
finish = true;
} else {
tmp.add(candidate);
}
String key = reverse ? candidate : str;
String value = reverse ? str : candidate;
if (! map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(value);
}
// restore after processing
chars[i] = old;
}
}
if (!finish) {
// Switch the start and end if size from start is bigger;
if (tmp.size() > end.size()) {
bfs(map, end, tmp, dicts, !reverse);
} else {
bfs(map, tmp, end, dicts, reverse);
}
}
}
private void dfs (Map<String, List<String>> map,
List<List<String>> result , List<String> subList,
String beginWord, String endWord) {
if(beginWord.equals(endWord)) {
result.add(new ArrayList<>(subList));
return;
}
if (!map.containsKey(beginWord)) {
return;
}
for (String word : map.get(beginWord)) {
subList.add(word);
dfs(map, result, subList, word, endWord);
subList.remove(subList.size() - 1);
}
}
}
Шаг 1: Пройдите по графику от источника по BFS и назначьте каждому узлу минимальное расстояние от источника
Шаг 2: расстояние, назначенное целевому узлу, является самой короткой длиной
Шаг 3: Из источника выполните поиск DFS по всем путям, где минимальное расстояние увеличивается один за другим, пока не будет достигнут целевой узел или не будет достигнута самая короткая длина. Печатайте путь всякий раз, когда достигается целевой узел.
Как насчет этого: я нашел это в интернете
BFS останавливается, когда вы найдете то, что вы хотите.
Вы должны изменить алгоритм, чтобы он продолжал свое выполнение, когда был найден первый путь. (удалить return Скажите и сохраните путь как-нибудь.
Вы можете завершить выполнение после проверки последнего узла уровня, у которого есть конечные узлы кратчайших путей. (Все конечные узлы кратчайших путей находятся на одном уровне)
Также существует известный алгоритм, который находит все кратчайшие пути:
Алгоритм Флойда – Варшалла (имеет псевдокод)