Почему нельзя использовать DFS для поиска кратчайших путей в невзвешенных графах?

Я понимаю, что использование DFS «как есть» не найдет кратчайшего пути в невзвешенном графе.

Но почему настройка DFS позволяет ему находить кратчайшие пути в невзвешенных графах с такой безнадежной перспективой? Все тексты на эту тему просто утверждают, что это невозможно сделать. Я не уверен (не попробовав сам).

Знаете ли вы какие-либо модификации, которые позволят DFS находить кратчайшие пути в невзвешенных графах? Если нет, то что это за алгоритм, который делает его таким сложным?

Единственный элемент поиска в глубину, который вы настраиваете, - это порядок, в котором исследуются дети. Обычная версия работает в произвольном порядке, то есть в том порядке, в котором хранятся дочерние элементы.

Единственная возможная альтернатива (к кратчайшим путям), которую я могу придумать, - это жадный подход, который смотрит на детей в порядке их расстояния от текущего узла (от маленького к большому). Легко построить контрпример для этого правила:

^{[ источник ]}

Теперь, это не доказательство того, что не существует стратегии выбора следующего ребенка, который будет исследован, который заставит DFS находить кратчайшие пути.

Однако, независимо от правила… вы можете построить графы, в которых DFS фиксируют длинный обход на самом первом узле, как я это делал для жадного правила. Присвоить ребра и веса , такие , что правило выбирает для посещения первый и назначить на вес больше , чем один из . Следовательно, вполне вероятно, что DFS никогда не сможет найти кратчайшие пути (в общих графах).( s , a ) a ( a , b ) ( s , t $(s,t)$$(s,a)$$a$$(a,b)$$(s,t)$

Обратите внимание, что поскольку вы можете выразить каждый взвешенный граф (с положительным целым числом) как невзвешенный граф - просто замените ребра стоимостью на цепочку с узлами - те же примеры работают с DFS на невзвешенных графах. Здесь ситуация на самом деле еще более безрадостная: без весов, что DFS может использовать для определения следующего ребенка, который посетит?с - $c$$c-1$

1. Пока правило является детерминированным. Если это не так, он явно не всегда может найти кратчайшие пути.

Ширина -first-поиск является алгоритмом , который найдет кратчайший путь в невзвешенном графике.

Существует простой способ перехода от DFS к алгоритму, который найдет кратчайшие пути на невзвешенном графике. По сути, вы заменяете стек, используемый DFS, очередью. Однако полученный алгоритм больше не называется DFS. Вместо этого вы осуществите поиск в ширину.

Приведенный выше параграф дает правильную интуицию, но немного упрощает ситуацию. Легко написать код, для которого простой своп дает реализацию поиска в ширину, но также легко написать код, который на первый взгляд выглядит как правильная реализация, но на самом деле это не так. Вы можете найти связанный cs.SE вопрос о BFS против DFS здесь . Вы можете найти хороший псевдокод здесь.

Вы можете!!!

Пометьте узлы как посещенные, когда вы проходите глубину, и снимите отметку, когда вы возвращаетесь, возвращаясь, когда вы обнаруживаете, что другие ветви повторяют то же самое.

Сохраните стоимость / путь для всех возможных поисков, где вы нашли целевой узел, сравните все такие затраты / путь и выберите самый короткий.

Большая (и я имею в виду БОЛЬШОЙ) проблема с этим подходом заключается в том, что вы будете посещать один и тот же узел несколько раз, что делает dfs очевидным плохим выбором для алгоритма кратчайшего пути.

У BFS есть приятное свойство, заключающееся в том, что он будет проверять все ребра от корня и сохранять минимальное расстояние от корня до других узлов, но dfs просто переходит к первому соседнему узлу и идет по глубине. Вы МОЖЕТЕ изменить DFS, чтобы получить кратчайший путь, но в итоге вы получите только алгоритм, который будет иметь более высокую временную сложность или в конечном итоге сделает то же самое, что и BFS

С помощью DFS можно найти путь между двумя вершинами с минимальным количеством ребер. мы можем применить подход уровня

Вы можете

просто пройтись по графику в режиме DFS и проверить

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Вот ссылка для полного решения