Я работаю над реализацией алгоритма Дейкстры, чтобы получить кратчайший путь между взаимосвязанными узлами в сети маршрутов. У меня есть работа. Он возвращает все кратчайшие пути ко всем узлам, когда я передаю старт node в алгоритм.
Мой вопрос: Как можно получить все возможные пути от node A, чтобы сказать node G или даже все возможные пути от node A и обратно до node A
Поиск всех возможных путей - трудная проблема, так как существует экспоненциальное число простых путей. Даже поиск k-го кратчайшего пути [или самого длинного пути] NP-Hard.
Одним из возможных решений для поиска всех путей [или всех путей до определенной длины] от s до t является BFS, без сохранения набора visited или для взвешенной версии - вы можете использовать единообразный поиск стоимости
Обратите внимание, что также в каждом графике, который имеет циклы [это не DAG], может быть бесконечное количество путей между s и t.
Я дам вам (несколько небольшую) версию (хотя и понятную, я думаю) научного доказательства того, что вы не можете сделать это в течение приемлемого промежутка времени.
Что я докажу, так это то, что временная сложность перечисления всех простых путей между двумя выбранными и разными узлами (например, s и t) в произвольном графе G не является полиномиальной. Обратите внимание, что, поскольку мы заботимся только о количестве путей между этими узлами, стоимость кросс неважна.
Уверен, что если граф имеет некоторые хорошо отобранные свойства, это может быть легко. Однако я рассматриваю общий случай.
Предположим, что у нас есть полиномиальный алгоритм, который перечисляет все простые пути между s и t.
Если G подключен, список не пуст. Если G нет, а s и t находятся в разных компонентах, очень легко перечислить все пути между ними, потому что их нет! Если они находятся в одном компоненте, мы можем сделать вид, что весь граф состоит только из этого компонента. Поэтому предположим, что G действительно подключен.
Количество перечисленных путей должно быть многочленным, иначе алгоритм не смог бы вернуть мне все. Если он перечисляет все из них, он должен дать мне самый длинный, так что он там. Имея список путей, можно применить простую процедуру, чтобы указать мне этот самый длинный путь.
Мы можем показать (хотя я не могу думать о связном способе сказать это), что этот самый длинный путь должен пересекать все вершины G. Таким образом, мы только что нашли гамильтоновский путь с полиномиальной процедурой! Но это хорошо известная проблема NP-hard.
Затем мы можем заключить, что этот полиномиальный алгоритм, который, как мы думали, мы имели, вряд ли существует, если P = NP.
Я реализовал версию, где он в основном находит все возможные пути от одного node к другому, но он не учитывает никаких возможных "циклов" (график, который я использую, цикличен). Таким образом, ни один node не появится дважды в одном и том же пути. И если граф был ацикличным, то, полагаю, вы могли бы сказать, что он находит все возможные пути между этими двумя узлами. Кажется, что он работает отлично, и для моего размера графа ~ 150 он работает почти мгновенно на моей машине, хотя я уверен, что время работы должно быть чем-то вроде экспоненциального, и поэтому оно начнет быстро замедляться, поскольку график становится больше.
Вот некоторый Java-код, который демонстрирует, что я реализовал. Я уверен, что должны быть более эффективные или элегантные способы сделать это.
Stack connectionPath = new Stack();
List<Stack> connectionPaths = new ArrayList<>();
// Push to connectionsPath the object that would be passed as the parameter 'node' into the method below
void findAllPaths(Object node, Object targetNode) {
for (Object nextNode : nextNodes(node)) {
if (nextNode.equals(targetNode)) {
Stack temp = new Stack();
for (Object node1 : connectionPath)
temp.add(node1);
connectionPaths.add(temp);
} else if (!connectionPath.contains(nextNode)) {
connectionPath.push(nextNode);
findAllPaths(nextNode, targetNode);
connectionPath.pop();
}
}
}
Здесь - алгоритм, который находит и печатает все пути от s до t, используя модификацию DFS. Кроме того, динамическое программирование может быть использовано для подсчета количества возможных путей. Псевдокод будет выглядеть следующим образом:
AllPaths(G(V,E),s,t)
C[1...n] //array of integers for storing path count from 's' to i
TopologicallySort(G(V,E)) //here suppose 's' is at i0 and 't' is at i1 index
for i<-0 to n
if i<i0
C[i]<-0 //there is no path from vertex ordered on the left from 's' after the topological sort
if i==i0
C[i]<-1
for j<-0 to Adj(i)
C[i]<- C[i]+C[j]
return C[i1]
Обычно вы этого не хотите, потому что есть экспоненциальное число из них в нетривиальных графах; если вы действительно хотите получить все (простые) пути или все (простые) циклы, вы просто найдете один (прогуливая график), а затем возвращайтесь к другому.
Я думаю, что вы хотите, это какая-то форма алгоритма Форда-Фулкерсона, основанная на BFS. Он используется для вычисления максимального потока сети, путем нахождения всех путей расширения между двумя узлами.
http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Я предполагаю, что вы хотите найти "простые" пути (путь прост, если в нем не появляется node, за исключением, возможно, первого и последнего).
Поскольку проблема NP-hard, вы можете захотеть сделать вариант поиска по глубине.
В принципе, сгенерируйте все возможные пути из A и проверьте, попадают ли они в G.
Там хорошая статья, которая может ответить на ваш вопрос/только она печатает пути, а не собирает их /. Обратите внимание, что вы можете экспериментировать с образцами С++/Python в онлайн-среде.
http://www.geeksforgeeks.org/find-paths-given-source-destination/
Этот вопрос сейчас немного старый... но я брошу свою шляпу в кольцо.
Я лично нашел алгоритм формы find_paths[s, t, d, k] полезным, где:
Использование вашей формы языка программирования бесконечности для d и k даст вам все пути.
§ Очевидно, что если вы используете ориентированный граф и хотите все неориентированные пути между s и t, вам придется запускать эти два способа:
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Мне лично нравится рекурсия, хотя это может быть сложно несколько раз, в любом случае сначала позволяет определить нашу вспомогательную функцию:
def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
current_path.append(current)
if current_depth > max_depth:
return
if current == goal:
if len(paths_found) <= number_of_paths_to_find:
paths_found.append(copy(current_path))
current_path.pop()
return
else:
for successor in graph[current]:
self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)
current_path.pop()
С этой точки зрения основная функция тривиальна:
def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found)
Во-первых, обратите внимание на несколько вещей:
[] - неинициализированный список, замените его эквивалентом для выбранного вами языка программирования.paths_found передается ссылкой. Понятно, что функция рекурсии ничего не возвращает. Обращайтесь с этим соответствующим образом.graph принимает некоторый вид структуры hashed. Существует множество способов реализации графика. В любом случае graph[vertex] получает список смежных вершин в ориентированном графе - соответствующим образом отрегулируйте.