Давайте возьмем этот график в качестве примера, где поиск должен начинаться с a , а целевой узел - c:
DFS
Предполагая, что дочерние элементы узла перемещаются в их лексическом порядке, DFS будет посещать узлы в порядке a, b, c, d, e
Он найдет эти расстояния:
a: 0
b: 5
c: 13
d: 8
Затем из d он снова увидит c и обновит его до 12
Далее:
e: 1
С e он снова увидит b и обновит его до 3. Но тогда DFS не дотягивает и до видя влияние этого изменения на узлы c и d .
алгоритм Дейкстры
Дейкстры, с другой стороны, будет посещать узлы в следующем порядке:
a: 0
e: 1
b: 3
Тогда он возьмет ребро с весом 5, но увидит, что b уже был посещен, и проигнорирует его. Тогда:
d: 6
c: 10
... и цель была найдена с правильным расстоянием.
BFS
Просто чтобы ответить на ваш комментарий ниже: BFS также не найдет правильный путь, потому что BFS не учитывает (общие) веса; он просто минимизирует количество ребер на пути.
BFS будет посещать узлы следующим образом:
a: 0
b: 5
e: 1
c: 13
... и остановится на этом. Если вы не остановитесь, а продолжите (с возможностью перезаписи), процесс продолжится:
d: 8
Затем он увидит b с e и обновит:
b: 3
Однако, поскольку b уже был посещен, BFS не увидит влияния, которое это изменение оказывает на c и d .
Он также видит c с d и обновления c до 12. Тогда для BFS больше нечего делать и явно результат неправильный.