1

На Википедии есть растолковка алгоритма Дейкстры в действии.

Судя по финальному просчёту должно получиться движение по красным наименьшим вершинам 0 => 7 => 9 => 11 => 20 => 20

введите сюда описание изображения

НО. Если не использовать алгоритм и не высчитывать вершину и всегда двигаться просто по наименьшему ребру, получается такое же движение 0 => 7 => 9 => 11 => 20 => 20.

Выходит тоже самое движение без использования алгоритма Дейкстры. Зачем тогда нужен этот алгоритм или я чего то не понимаю?

1 ответ 1

7

Вот вам граф:

   1
*-----*
|     |
|1    |1
|     |
|  2  |
O-----*

Двигаясь просто "по наименьшему ребру", вы получите расстояние между нижними вершинами - 3, не смотря на то, что прямое ребро между ними короче.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.