@empty_project

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

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

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

Войти через центр авторизации
Похожие вопросы
SegmentStream Москва
от 250 000 до 350 000 руб.
Aurora Infinity Москва
от 60 000 до 120 000 руб.
HTML Academy Санкт-Петербург
от 150 000 до 180 000 руб.