@empty_project

Как найти ВСЕ кратчайшие пути между двумя вершинами?

Как можно в неориентированном графе найти все кратчайшие пути между двумя вершинами? Проблема вот в чем: может быть ситуация, когда из некоторой вершины u до вершины v есть несколько кратчайших путей и все они одинаковой длины. Что делать в такой ситуации? Вот пример такого графа: 5c2270ea12ec6230470504.jpeg
Здесь из вершины 1 до вершины 3 три кратчайших пути одинаковой длины: 1-3, 1-4-5-3, 1-5-3
  • Вопрос задан
  • 1602 просмотра
Решения вопроса 1
longclaps
@longclaps
А зачем?
Представь себе шахматную доску, твои вершины - клетки, рёбра - границы смежных клеток и только они, переход шаг_влево/шаг_вправо/шаг_вверх/шаг_вниз.
Сколько существует кратчайших путей с левой нижней клетки в правую верхнюю? спойлер: 3432
А если вообразить аналогичный трёхмерный куб? 399072960
Вывод: задача хреново поставлена.
UPDATE
Для наглядности, пусть из одной из нужных вершин выходят 3 грани.
Строишь кратчайший путь, он проходит через первую из 3 граней. Путь запоминаешь, грань перерезаешь.
Строишь кратчайший путь, он проходит через вторую грань. Если он равновелик первому - запоминаешь, вторую грань перерезаешь, если больше - вторую и третью грани можешь совсем выкинуть.
Достаёшь первый путь, восстанавливаешь первую грань, идёшь по пути дальше до вершины с развилкой. режешь грань кратчайшего пути - ну, понятно, рекурсия.
На вырожденном графе, как я и обещал, хана.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@crazywu
Мне кажется, что удобнее всего использовать обход в ширину. Записывая вес и путь до каждой встретившейся вершины.
В конечной точке соберутся все варианты.
Только эта штука будет жутко кушать память и не помешало бы сделать некоторые оптимизации:
-удалять/не записывать более длинные пути
-обьединять при дальнейшем поиске пути "слившиеся" в одной вершине
(Это то, что сразу приходит на ум, может есть ещё какие-то варианты)
Ответ написан
Комментировать
@Zanak
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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