Получение кратчайшего пути динамического графа

24

Я изучаю кратчайшие пути в ориентированных графах в настоящее время. Существует много эффективных алгоритмов для поиска кратчайшего пути в сети, например, dijkstra или bellman-ford. Но что, если график является динамическим? Говоря динамически, я имею в виду, что мы можем вставлять или удалять вершины во время выполнения программы. Я пытаюсь найти эффективный алгоритм для обновления кратчайших путей от вершины до любой другой вершины после вставки ребра без необходимости повторного запуска алгоритма кратчайшего пути в новом графе. Как я могу это сделать? Заранее спасибо.vue

  • Примечание: изменения могут быть сделаны после первой итерации алгоритма
  • Примечание [2]: два узла приведен, источник и цели. Мне нужно найти кратчайший путь между этими узлами. Когда график обновляется, мне нужно только обновить , который является кратчайшим путем между и .stπ(s,t)st
  • Примечание [3]: меня интересует только случай вставки края.

Формальное определение : Дан граф . Определим операцию обновления , как 1) вставку кромки к или 2) аа удаление краевой из . Цель состоит в том, чтобы эффективно найти стоимость всех пар кратчайших путей после операции обновления. Под эффективностью мы подразумеваем как минимум лучшее, чем выполнение алгоритма All-Pairs-Shortest-Path, такого как алгоритм Беллмана-Форда, после каждой операции обновления.e E e EG=(V,E)eEeE


Редактировать: Ниже приведена упрощенная версия задачи:

Дан взвешенный граф , состоящий из однонаправленных ребер и двух критических вершин и . Набор кандидатов двунаправленных ребер также дается. Я должен построить ребро чтобы минимизировать расстояние от до .s t CG(V,E)stCs t(u,v)Cst

Ронтогианнис Аристофанис
источник
Дополнительные уточняющие вопросы: остаются ли конечные точки вашего пути фиксированными каждый раз? Вас интересует только случай вставки ребер или произвольные изменения в графике? Я думаю, что есть ответы на ваш вопрос, но, к сожалению, я не знаю, где искать. Быстрый поиск в Google показывает эти слайды, которые кажутся очень полезными, и эту статью: «кратчайшие пути на динамических графиках» (надеюсь, что ссылка работает). (u,v)
Усул

Ответы:

14

Проблема, как вы, наверное, заметили, довольно сложная. Проверка в Интернете приведет к некоторым сложным случаям, которые, вероятно, вам не понадобятся. Вот решение - по мере необходимости (т.е. вам не нужно пересчитывать все с нуля).

в случае добавления ребра - затем с использованием уже построенной матрицы расстояний - сделайте следующее:(u,v)

Для каждой пары узлов и y проверьте, что d ( ( x , u ) ) + c ( ( u , v ) ) + d ( ( v , y ) ) < d ( ( x , y ) ) - это можно сделать в O ( n 2 ), так как вы сравниваете каждую пару узлов.xyd((Икс,U))+с((U,v))+d((v,Y))<d((Икс,Y))О(N2)

Для случая удаления ребер: Учитывая уже построенную матрицу расстояний, вы можете иметь для каждого узла дерево кратчайшего пути с корнем в u . Если удаленное ребро e не находится в этом дереве, то кратчайшие пути от u ко всем остальным не затрагиваются (они остаются теми же).UUеU

Если находится в дереве кратчайших путей u , то для каждого узла v такого, что кратчайший путь π ( u , v ) включает в себя e , пути изменятся. Поэтому вычислите кратчайший путь от u до v . Теперь повторите предыдущее для каждого узла - это не лучшее решение. На самом деле, в худшем случае это асимптотически эквивалентно выполнению всех задач с нуля, но в среднем может быть лучше. еUvπ(U,v)еUv

если вы хотите получить лучшие результаты, чем это, посмотрите на:

  1. Деметреску, Камил и Джузеппе Ф. Итальяно. «Новый подход к динамике всех пар кратчайших путей». Журнал ACM (JACM) 51,6 (2004): 968-992. (можно найти бесплатно в Google)

  2. или взгляните на этот красиво написанный опрос

AJed
источник
17

Проблема, которую вы задаете, - это хорошо известные алгоритмические проблемы. На самом деле все еще открыто, насколько сложна эта проблема. Также вы должны знать, что существуют разные варианты этой проблемы. В отличие от того, что вы просите, обычно возвращаются только расстояния, тогда как вы запрашиваете самые короткие пути. Обратите внимание, что эти пути могут быть уже очень длинными. Алгоритмы динамического графа различают только удаления ребер (алгоритмы убывания dg), только вставки ребер (алгоритмы инкрементного dg) и вставки и удаления ребер (полностью динамические алгоритмы dg). Таким образом, вы заинтересованы в дополнительных алгоритмов.

Алгоритмы, упомянутые в посте AJed, немного устарели. Thorup предлагает более новые результаты, краткий обзор см. Здесь, на странице 8 . Лучший в настоящее время полностью динамический точный алгоритм APSP от Thorup (для дистанционных запросов, а не для пути) требует амортизированного времени обновления при поддержке O ( 1 ) наихудшее время запроса. Обратите внимание, что если у вас есть O ( n log n )О(N2(журналN+журнал2(1+м/N))О(1)О(NжурналN)ребер, то вы можете просто пересчитать с нуля с помощью Dijkstra и Fibonacci-heaps и получить то же время выполнения, что и в алгоритме Thorup. Так что если ваши графики не слишком плотные, я бы порекомендовал использовать Dijkstra.

Я не знаю ни одного более дополнительного алгоритм. Но вы должны сделать поиск в Интернете, если существуют более новые результаты для этой специализированной проблемы.

A.Schulz
источник
Мне не нужно обновлять все кратчайшие пути в графе, но только между данной парой . Есть ли что-нибудь лучше для этого? (s,T)
Rontogiannis Aristofanis
@RondogiannisAristophanes на самом деле то, что было предложено до сих пор, является каким-то лучшим. Взгляните на эту статью, в которой утверждается, что: «инкрементные и декрементальные задачи с кратчайшими путями из одного источника для взвешенных направленных или ненаправленных графов, в строгом смысле, по меньшей мере так же сложны, как статические кратчайшие пути из всех пар проблема «. (если честно, я только что прочитал вступление) - ссылка: «О динамических проблемах кратчайших путей», Родитти и Цвик - но не могли бы вы сказать нам, какая именно у вас проблема? какой конкретный сценарий? что ты делаешь до сих пор? - может быть, мы можем помочь вам лучше.
AJed
@RondogiannisAristophanes, чем выше производительность, тем сложнее ее реализовать (в большинстве случаев), а иногда и в практических приложениях вам не нужно слишком много улучшать производительность.
AJed
@AJed Я отредактировал свой пост, чтобы включить упрощенное описание проблемы.
Rontogiannis Aristofanis
5

Я считаю, что алгоритм AD * может вам помочь.

http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

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

AD * подчеркивает: это «в любое время», что означает, что оно может дать вам «неоптимальное решение» очень быстро, хотя оно может быть не лучшим. Однако, если дать достаточно времени, он вернет оптимальное решение. Кроме того, вы можете ограничить неоптимальное решение не хуже, чем оптимальное решение некоторой определенной пользователем константой. Это дает вам возможность использовать это в сценарии планирования в режиме реального времени, когда иметь хорошее решение (где теоретически ограничено «хорошо») лучше, чем вообще не иметь решения.

http://www.cs.cmu.edu/~maxim/software.html

Виктор
источник