Какой смысл выбирать ближайший узел в алгоритме Дейкстры?

Question

Во всех статьях, которые я прочитал, сосед, обрабатывающий первым, является "ближайшим" соседом. Но, наконец, необходимо посетить все узлы, чтобы выяснить все возможные пути. Итак, вопрос - почему мы это делаем? Я полагаю, что тот же результат может быть достигнут, если мы просто пройдем по Graph BFS и проведем расчет затрат. Например:

первый шаг- 0, таблица затрат: 2 - 6 | 3 - 2 |

второй шаг- 2, таблица затрат: 2 - 6 | 3 - 2 | 1 - 9 |

третий шаг- 3, таблица затрат: 2 - 6 | 3 - 2 | 1 - 9 | 4 - 12 |

четвертый шаг - таблица затрат: 2 - 6 | 3 - 2 | 1 - 9 | 4 - 12 | 5 - 12 |

пятый шаг- 4, таблица затрат: 2 - 6 | 3 - 2 | 1 - 9 | 4 - 12 | 5 - 12 |

С простым обходом BFS был найден самый дешевый способ. Чего мне не хватает?

Answer 1

Предположим, что путь от A до B и B до C равен стоимости 1, а прямой маршрут от A до C равен стоимости 3. (В реальном мире первые две дороги проходят в обход горы, а третья - крошечная тропа через горный перевал.)

Дейкстра направит вас A -> B -> C на общую сумму 2, а BFS направит вас A -> C на общая стоимость 3.

Поэтому сначала нужно обработать наименьшую стоимость, чтобы получить правильный ответ.

Answer 2

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