Можем ли мы найти k кратчайших путей между всеми парами быстрее, чем многократное решение парной задачи?

9

Я хочу создать кратчайшего пути ( k будет меньше 10) между всеми парами в графе. График (на самом деле карта метро):kk

  • положительно взвешенный
  • ненаправленный
  • редкий
  • около 100 узлов

Мой текущий план - применить k каждой паре маршрутизацию по кратчайшему пути ; Сейчас я ищу более эффективную альтернативу (возможно, с динамическим программированием).

algorithms graphs optimization shortest-path Франклин Ю
источник
3
Честно говоря, для 100 вершин кажется маловероятным, что вам нужно что-то более эффективное, чем решение каждой из 45 000 парных задач.
Дэвид Ричерби

Ответы:

6

k

Задача всех парk

Это, кажется, довольно молодая область исследований. Недавнюю работу Агарвала и Рамачандрана можно найти на ArXiv [1]. Раздел «Предыдущая работа» также даст вам некоторое представление об истории проблемы.

Задача всех парk

Здесь, действительно, лучший выбор - просто неоднократно применять алгоритм Эппштейна [2]. Общее замечание о том, что повторное применение алгоритма для версии задачи из одного источника является наиболее быстрым, было уже сделано в 1977 году Э. Л. Лоулером [3]; Eppstein предоставляет самый быстрый алгоритм на сегодняшний день для этой подзадачи.

Ссылки

k

[2] Эппштейн Д. Нахождение k кратчайших путей. SIAM Journal of Computing 28, 2 (1999), 652–673.

[3] Лоулер, Е.Л. Комментарий к вычислению k кратчайших путей в графе. Сообщения ACM, 20 (8): 603–605, 1977.

выдумка
источник
Спасибо. Поскольку я работаю с картой метро, ​​мне нужно, чтобы они были простым путем (для моего программного обеспечения не имеет смысла направлять людей туда-сюда), поэтому я бы предпочел пойти с алгоритмом Яна .
Франклин Ю
Интересно и довольно удивительно, что, по-видимому, 10 000 случаев проблемы не могут быть решены быстрее, чем просто решение 10 000 отдельных случаев, один за другим.
gnasher729
идея путей с циклами, включенными в «кратчайшие пути», кажется нелогичной и необычной, потому что, по-видимому, существует эквивалентный «путь» с удаленным циклом, и также возникает вопрос, могут ли они быть эффективно построены из простых путей и т. д ...
Vzn