MykolaPetiukh
@MykolaPetiukh
Директор кафе

Поиск пути между точками для самых маленьких?

Что-то мой котелок не может уловить суть хоть того же алгоритма Дейкстры. Тупняк какой-то ловлю, пытаясь реализовать.
Может кто-то на пальцах пояснить?
  • Вопрос задан
  • 47 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Алгоритм прост: В процессе работы у нас есть вершины, до которых путь уже найден, вершины, до которых у нас есть кандидаты путей, и остальные вершины. Изначально только начальная вершина находится в кандидатах.

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

Почему это работает? У нас поддерживаются кандидаты путей через уже готовые вершины + одно ребро. Самая близкая вершина из кандидатов 100% имеет именно такой кратчайший путь, потому что если бы был какой-то другой путь, то он бы проходил через какую-то из других вершин-кандидатов. Но до них пути уже длинее. Но тут используется ограничение алгоритма - все ребра неотрицательные.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
DDoS-GUARD Ростов-на-Дону
от 70 000 до 120 000 ₽
OZON Москва
от 180 000 до 270 000 ₽
Softaria Новосибирск
от 100 000 до 150 000 ₽