Vorschläge für KSPA auf ungerichteten Graphen

Question

Es gibt eine benutzerdefinierte Implementierung von KSPA, die neu geschrieben werden muss. Die aktuelle Implementierung verwendet einen modifizierten Dijkstra-Algorithmus, dessen Pseudo-Code wird grob im Folgenden erläutert. Es wird allgemein als KSPA mit kantenLöschStrategie i so denken bekannt. (Ich bin ein Neuling in Graph-Theorie).

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

Wie ich den Algorithmus verstehen, KTH kürzesten Weg zu bekommen, ‚k-1‘ SPTs sind zwischen jedem Quelle-Ziel-Paar und ‚k-1‘ Kanten jeweils von einem SPT gefunden werden sollen, für jede Kombination gleichzeitig gelöscht werden . Offensichtlich dieser Algorithmus hat die kombinatorische Komplexität und verstopft den Server auf großen Graphen. Leute vorgeschlagen mir Eppstein-Algorithmus ( http: //www.ics. uci.edu/~eppstein/pubs/Epp-SJC-98.pdf ). Aber dieses Whitepaper zitiert eine ‚Digraph‘ und ich habe keine Erwähnung, dass es nur für Digraphe funktioniert. Ich wollte nur die Leute hier fragen, ob jemand diesen Algorithmus auf einem ungerichteten Graphen verwendet hat?

Wenn nicht, gibt es gute Algorithmen (in Bezug auf die Zeit-Komplexität) KSPA auf einem ungerichteten Graphen zu implementieren?

Vielen Dank im Voraus,

Answer 1

Zeitkomplexität: O (K * (E * log (K) + V * log (V)))

Speicherkomplexität von O (K * V) (+ O (E) zum Speichern der Eingabe).

Wir führen eine modifizierte Djikstra wie folgt:

• Für jeden Knoten, anstatt die besten derzeit bekannt Kosten für den Weg vom Start-Knoten zu halten. Wir halten die besten K Routen von Startknoten
• Wenn ein Knoten aktualisieren Nachbarn, wir überprüfen nicht, ob es die besten derzeit bekannten Weg verbessert (wie Djikstra der Fall ist), überprüfen wir, ob es das Schlimmste der K verbessert‘besten derzeit bekannten Weg.
• Nachdem wir bereits die erste einer Knoten K besten Routen verarbeitet werden, brauchen wir keine K besten Routen zu finden, aber nur haben K-1 bleiben, und nach einem anderen K-2. Das ist, was ich genannt K‘.
• Für jeden Knoten wir zwei Prioritätswarteschlangen für den besten derzeit bekannten Weglängen ‚K halten.
  • In einer Prioritätswarteschlange der kürzeste Weg nach oben zeigt. Wir verwenden diese Prioritätswarteschlange zu bestimmen, welche der K‘am besten ist, und wird als Vertreter der Knoten in den regulären Djikstra des Prioritäts-Warteschlangen verwendet werden.
  • Im anderen Prioritätswarteschlange der längste Weg nach oben zeigt. Wir verwenden diese zu Kandidatenpfade zu den schlimmsten der Wege ‚K zu vergleichen.