Suggestions pour KSPA sur un graphe non orienté

Question

Il existe une implémentation personnalisée de KSPA qui doit être réécrite. L'implémentation actuelle utilise un algorithme de Dijkstra modifié dont le pseudo-code est expliqué ci-dessous. Il est communément appelé KSPA en utilisant la stratégie de suppression de bord je pense. (je suis un novice en théorie des graphes).

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 

que je comprends l'algorithme, pour obtenir kième plus court chemin, SPT « k-1 » se trouvent entre chaque paire source-destination et « k-1 » bords chacun d'un SPT doivent être supprimés simultanément pour chaque combinaison. Il est clair que cet algorithme a une complexité combinatoire et obstrue le serveur sur de grands graphiques. Les gens m'ont suggéré l'algorithme d'Eppstein (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf). Mais ce livre blanc cite un «digramme» et je n'ai pas vu mentionner qu'il ne fonctionne que pour les digrammes. Je voulais juste demander aux gens si quelqu'un a utilisé cet algorithme sur un graphe non orienté? Sinon, y a-t-il de bons algorithmes (en termes de complexité temporelle) pour implémenter KSPA sur un graphe non orienté?

Merci à l'avance,

Answer 1

complexité Temps: O (K * (E * log (K) + V * log (V)))

complexité de la mémoire de O (K * V) (+ O (E) pour stocker l'entrée).

Nous effectuons un Djikstra modifié comme suit:

• Pour chaque nœud, au lieu de garder le meilleur rapport coût actuellement connu de la route depuis le début nœud. Lors de la mise à jour des voisins d'un nœud, nous ne vérifions pas s'il améliore le meilleur chemin actuellement connu (comme le fait Djikstra), nous vérifions s'il améliore le pire du K '. chemin actuellement connu.
• Après avoir déjà traité le premier des K meilleurs itinéraires d'un nœud, nous n'avons pas besoin de trouver K meilleurs itinéraires, mais seulement K-1 restant, et après un autre K-2. C'est ce que j'ai appelé K '.
• Pour chaque nœud, nous conserverons deux files d'attente prioritaires pour les K 'meilleures longueurs de chemin actuellement connues.
  • Dans une file d'attente prioritaire, le chemin le plus court est en haut. Nous utilisons cette file d'attente prioritaire pour déterminer lequel des K 'est le meilleur et sera utilisé dans les files d'attente prioritaires du Djikstra comme représentant du nœud.
  • Dans l'autre file d'attente prioritaire, le chemin le plus long est en haut. Nous utilisons celui-ci pour comparer les chemins candidats au pire des chemins K '.