Предложения по KSPA на неориентированном графе

Question

Существует пользовательская реализация 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-й кратчайший путь, ‘k-1’ SPT должны быть найдены между каждой парой источник-назначение, а ‘k-1’ ребра, каждое из одного SPT, должны быть удалены одновременно для каждой комбинации.Очевидно, что этот алгоритм обладает комбинаторной сложностью и засоряет сервер большими графиками.Люди предложили мне алгоритм Эппштейна (http://www.ics.uci.edu /~эппштейн/пабы/Epp-SJC-98.pdf).Но в этом техническом документе упоминается "орграф", и я не видел упоминания о том, что он работает только для орграфов.Я просто хотел спросить присутствующих здесь людей, использовал ли кто-нибудь этот алгоритм на неориентированном графике?

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

Заранее благодарю,

Answer 1

Временная сложность:O(K*(E*log(K)+V*log(V)))

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

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

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