Алгоритм поиска кратчайшего пути в графе

Имеется неориентированный невзвешенный граф, в котором требуется найти кратчайший путь между двумя заданными вершинами. Также имеется условие, что при прохождении некоторых ребер (известны заранее) могут появляться или исчезать какие-то определенные, также известные заранее, ребра. Подскажите, подойдет ли для этой задачи алгоритм Дейкстры?

  • Вопрос задан
  • 5214 просмотров
Пригласить эксперта
Ответы на вопрос 3
@Mercury13
Программист на «си с крестами» и не только

Если подвижных мостов мало, можно каждую вершину размножить в 2b экземплярах (b — кол-во мостов). Тогда пойдёт даже не Дейкстра, а обычный поиск в ширину.

Если два моста «сцеплены» друг с другом и наводятся/разводятся одновременно, то в b они идут одной штукой.

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

Ответ написан
afiskon
@afiskon

В первом приближении кажется, что здесь нужно применить либо поиск в ширину, либо алгоритм A*. С доверительными состояниями в обоих случаях. Я здесь об этом писал в свое время.

Ответ написан
Комментировать
Goodilla
@Goodilla
Разработчик/архитектор веб приложений

По университету помню, использовали для решения алгоритм Коммивояжера или Муравьиный алгоритм. Оба работают, вопрос в реализации. Учитывая, что по логике они схожи, но не идентичны, осмелюсь предположить, что вполне возможна реализация с использованием данного алгоритма. Единственное, что два предыдущих алгоритма используются для поиска наикратчайшего пути по всему графу, в этом разница. Как вариант, можно попробовать алгоритм Левита.

Вопрос, если у Вас известны ребра, то почему граф не взвешенный? Возможно я что-то не понял, заранее прошу прощения.

Ответ написан
Комментировать
Ваш ответ на вопрос

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

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