Разве мы не можем найти кратчайший путь по DFS (модифицированной DFS) в невзвешенном графике? а если нет то почему?

Question

Говорят, что DFS не может использоваться для поиска кратчайшего пути в невзвешенном графе. Я прочитал несколько постов и блогов, но не удовлетворен, поскольку небольшая модификация в DFS может сделать это возможным.

Я думаю, что если мы будем использовать Модифицированную DFS таким образом, мы сможем найти кратчайшие расстояния от источника.

1. Инициализировать массив расстояний от корня с бесконечностью и расстояние корня от себя как 0.
2. Во время обхода мы отслеживаем нет. краев. При движении вперед шаг нет. ребер и в то время как обратная дорожка декремента нет. краев. И каждый раз проверяйте, если (dist (v)> dist (u) + 1), то dist (v) = dist (u) + 1.

Таким образом, мы можем найти кратчайшие расстояния от корня, используя DFS. И таким образом, мы можем найти его в O (V + E) вместо O (ElogV) Дейкстры.

Если я ошибаюсь в какой-то момент. Пожалуйста, скажите мне.

Answer 1

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

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

Рассмотрим граф с n узлами, пронумерованными от 1 до n. Пусть между каждым k и k + 1 будет грань. Также, позвольте 1 быть подключенным к каждому узлу.

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

Теперь попробуйте запустить алгоритм в своей голове или на компьютере с правами root 1. Сначала алгоритм достигнет n с шагом n-1, используя ребра между 1-2, 2-3 и так далее. Затем, после возврата, алгоритм переходит ко второму соседу 1, а именно 3. На этот раз будет n-2 шагов. Тот же процесс будет повторяться до тех пор, пока алгоритм, наконец, не увидит 1-n. Алгоритм потребует O (n ^ 2), а не O (n) шагов, чтобы закончить. Помните, что V = n & E = 2 * n - 3. Так что это не O (V + E).

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

O (V ^ 2) не так уж и плохо. Особенно если граф плотный. Но поскольку BFS уже дает ответ в O (V + E), никто не использует DFS для расчета кратчайшего расстояния.

Answer 2

В невзвешенном графике вы можете использовать поиск в ширину (не DFS), чтобы найти кратчайшие пути за время O (E).

На самом деле, если все ребра имеют одинаковый вес, то алгоритм Дейкстры и поиск в ширину в значительной степени эквивалентны - метод lessKey () никогда не вызывается, и очередь с приоритетами может быть заменена на очередь FIFO, поскольку недавно добавленный вершины никогда не имеют меньшего веса, чем ранее добавленные.

Ваша модификация в DFS не работает, потому что, посетив вершину, вы больше не будете проверять ее потомков, даже если ее вес изменится. Вы получите неправильный ответ для этого графика, если будете следовать S-> A до S-> B

S---->A---->C---->D---->E---->T
 \               /
  ------->B-----/

Answer 3

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

Итак, предположим, что у вас есть треугольник с узлами A, B, C и вы хотите найти кратчайший путь от A до B. Одна из возможностей обхода DFS - A -> C -> B, и все готово. Это, однако, не самый короткий путь.