Имеется неориентированный невзвешенный граф, в котором требуется найти кратчайший путь между двумя заданными вершинами. Также имеется условие, что при прохождении некоторых ребер (известны заранее) могут появляться или исчезать какие-то определенные, также известные заранее, ребра. Подскажите, подойдет ли для этой задачи алгоритм Дейкстры?
Если подвижных мостов мало, можно каждую вершину размножить в 2b экземплярах (b — кол-во мостов). Тогда пойдёт даже не Дейкстра, а обычный поиск в ширину.
Если два моста «сцеплены» друг с другом и наводятся/разводятся одновременно, то в b они идут одной штукой.
А если мостов много и 2b — непозволительная трата, тогда интересно. Думаю, ничего, кроме эвристик, не поможет. Например, может случиться так, что кратчайший путь от включателя до всех мостов, которыми он управляет, посуху. Или мосты (в смысле управляемые) — это мосты (в смысле теории графов). Или что-нибудь ещё.
По университету помню, использовали для решения алгоритм Коммивояжера или Муравьиный алгоритм. Оба работают, вопрос в реализации. Учитывая, что по логике они схожи, но не идентичны, осмелюсь предположить, что вполне возможна реализация с использованием данного алгоритма. Единственное, что два предыдущих алгоритма используются для поиска наикратчайшего пути по всему графу, в этом разница. Как вариант, можно попробовать алгоритм Левита.
Вопрос, если у Вас известны ребра, то почему граф не взвешенный? Возможно я что-то не понял, заранее прошу прощения.
Средний
Простой
Средний
Простой
