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

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы