Suggestions pour KSPA sur un graphe non dirigé

Question

Il existe une implémentation personnalisée de KSPA qui doit être réécrite. La mise en œuvre actuelle utilise un algorithme de Dijkstra modifié dont le pseudocode est expliqué en détail ci-dessous. Il est communément appelé KSPA en utilisant une 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

Si je comprends bien l’algorithme, pour obtenir le kème chemin le plus court, & # 8216; k-1 & # 8217; Des SPT doivent être trouvés entre chaque paire source-destination et & # 8216; k-1 & # 8217; les bords de chaque SPT doivent être supprimés simultanément pour chaque combinaison. Il est clair que cet algorithme a une complexité combinatoire et encrasse le serveur sur les 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 «digraphe» et je n’ai pas vu de mention que cela ne fonctionne que pour les digrammes. Je voulais juste demander aux gens ici si quelqu'un a utilisé cet algorithme sur un graphe non dirigé?

Si non, existe-t-il de bons algorithmes (en termes de complexité temporelle) pour implémenter KSPA sur un graphe non dirigé?

Merci d'avance,

Answer 1

Complexité temporelle: 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 conserver le meilleur coût de routage actuellement connu depuis le nœud de démarrage. Nous gardons les meilleures routes K du nœud de départ
• Lors de la mise à jour des voisins des noeuds, 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 meilleur chemin actuellement connu de K '.
• Une fois que nous avons déjà traité la première des meilleures routes K d'un nœud, nous n'avons plus besoin de trouver les meilleures routes K, il ne reste plus que K-1, et après un autre K-2. C'est ce que j'ai appelé K '.
• Pour chaque noeud, nous garderons 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 'convient le mieux et sera utilisé dans les files d'attente prioritaires de Djikstra habituelles en tant que 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 plus mauvais des chemins K '.