Как проследить пути между двумя узлами в данном графике один раз, если мы знаем, или выигрыш узнать длину пути между ними? (При рассмотрении матрицы смежности)Трассировка пути в графе между двумя узлами
Между смежности матрица и ширина первого поиска в поиске путей, которые эффективны?
Не могли бы вы дать шаги алгоритма.
Благодарим вас в Advance, Kamala.
Собственно, ответ будет зависеть от того, какой путь вы ищете.
Если вы ищете кратчайший путь, тогда вы можете попробовать реализовать Dijkstra's algorithm, который также работает очень быстро.
Если вы просто пытаетесь найти путь, независимо от его длины, то BFS - прекрасное решение, так как оно найдет его в «самом мелком» месте, хотя оно не гарантирует, что оно является самым коротким ,
Других вариантов для вас DFS, который будет искать первый для самых глубоких путей и Bellman-Ford, что также даст самый короткий путь, но в более общих ситуациях, чем Дейкстры, поэтому он будет медленнее.
Если вы хотите все возможные пути, то любой из этих алгоритмов можно переопределить для выполнения маркировки графика и, следовательно, получить все возможные пути.