Предложения для КСПА по ненаправленному графику - PullRequest
Новая
       12

Предложения для КСПА по ненаправленному графику

5 голосов
/ 06 мая 2009

Существует специальная реализация KSPA, которую необходимо переписать. Текущая реализация использует модифицированный алгоритм Дейкстры, псевдокод которого примерно описан ниже. Я думаю, что он широко известен как KSPA, использующий стратегию удаления краев. (Я новичок в теории графов). 

Step:-1.  Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here.
Step:-2.   Set k = 1
Step:-3.   Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List.
Step:-4.  Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination.
Step:-5.   Delete the combination of edges chosen in the above step temporarily from the graph in memory.
Step:-6.   Re-run Dijkstra for the same pair of nodes as in Step:-1.
Step:-7.   Add the resulting path into a temporary list of paths. Paths_List.
Step:-8.   Restore the deleted edges back into the graph.
Step:-9.   Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr.
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List).
Step:-11. k = k + 1 Go to Step:-3, until k < N.
Step:-12. STOP

Как я понимаю алгоритм, чтобы получить k-й кратчайший путь, SPT 'k-1' должны быть найдены между каждой парой источник-назначение, а ребра 'k-1', каждый из одного SPT, должны быть удалены одновременно для каждой комбинации , Очевидно, что этот алгоритм имеет комбинаторную сложность и забивает сервер на больших графах. Люди предложили мне алгоритм Эппштейна (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf).. Но в этом документе упоминается «орграф», и я не увидел упоминания о том, что он работает только для орграфов. Я просто хотел спросить здесь, кто-нибудь использовал этот алгоритм на неориентированный граф?

Если нет, существуют ли хорошие алгоритмы (с точки зрения сложности времени) для реализации KSPA на неориентированном графе?

Заранее спасибо,

1 Ответ

5 голосов
/ 25 августа 2009

Сложность времени: O (K * (E * log (K) + V * log (V)))

Сложность памяти O (K * V) (+ O (E) для хранения ввода).

Мы выполняем модифицированную Джикстру следующим образом:

  • Для каждого узла вместо сохранения лучшей на данный момент известной стоимости маршрута от начального узла. Мы сохраняем лучшие K маршрутов от стартового узла
  • При обновлении соседей узла мы не проверяем, улучшает ли он лучший на данный момент известный путь (как это делает Джикстра), мы проверяем, улучшает ли он наихудший из K 'лучшего на данный момент известного пути.
  • После того, как мы уже обработали первый из K лучших маршрутов узла, нам не нужно находить K лучших маршрутов, у нас остался только K-1, а после еще один K-2. Это то, что я назвал К '.
  • Для каждого узла мы будем хранить две очереди приоритетов для K 'лучших на данный момент известных длин путей.
    • В одной очереди с приоритетами кратчайший путь находится сверху. Мы используем эту очередь приоритетов, чтобы определить, какая из K 'является лучшей, и будет использоваться в очередях приоритетов обычной Джикстры в качестве представителя узла.
    • В другой очереди с приоритетами самый длинный путь находится сверху. Мы используем этот способ для сравнения возможных путей с худшими из путей K '.
...