Suggerimenti per KSPA sul grafico non indirizzato

Question

Esiste un'implementazione personalizzata di KSPA che deve essere riscritta. L'attuale implementazione utilizza un algoritmo di Dijkstra modificato il cui pseudocodice è approssimativamente spiegato di seguito. È comunemente noto come KSPA utilizzando la strategia di eliminazione dei margini, penso di sì. (Sono un novizio in teoria dei grafi).

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

Come capisco l'algoritmo, per ottenere il kth percorso più breve, si devono trovare SPT 'k-1' tra ciascuna coppia sorgente-destinazione e i bordi 'k-1' ciascuno da un SPT devono essere eliminati simultaneamente per ogni combinazione . Chiaramente questo algoritmo ha complessità combinatoria e ostruisce il server su grafici di grandi dimensioni. La gente mi ha suggerito l'algoritmo di Eppstein ( http: //www.ics. uci.edu/~eppstein/pubs/Epp-SJC-98.pdf ). Ma questo white paper cita un 'digrafo' e non ho visto la menzione che funziona solo per i digrafi. Volevo solo chiedere alla gente qui se qualcuno ha usato questo algoritmo su un grafico non indirizzato?

In caso contrario, esistono buoni algoritmi (in termini di complessità temporale) per implementare KSPA su un grafico non indirizzato?

Grazie in anticipo,

Answer 1

Complessità temporale: O (K * (E * log (K) + V * log (V)))

Complessità della memoria di O (K * V) (+ O (E) per la memorizzazione dell'ingresso).

Eseguiamo un Djikstra modificato come segue:

• Per ciascun nodo, invece di mantenere il costo del percorso attualmente più noto da start-node. Manteniamo le migliori rotte K dal nodo iniziale
• Durante l'aggiornamento dei vicini di un nodo, non controlliamo se migliora il percorso attualmente più conosciuto (come fa Djikstra), controlliamo se migliora il peggio del percorso più conosciuto di K.
• Dopo aver già elaborato la prima delle migliori rotte K di un nodo, non abbiamo bisogno di trovare le migliori rotte K, ma rimane solo K-1 e dopo un'altra K-2. Questo è quello che ho chiamato K '.
• Per ogni nodo manterremo due code prioritarie per le lunghezze di percorso più conosciute di K attualmente.
  • In una coda prioritaria il percorso più breve è in cima. Usiamo questa coda di priorità per determinare quale delle K 'è la migliore e verrà usata nelle normali code di priorità di Djikstra come rappresentante del nodo.
  • Nell'altra coda di priorità il percorso più lungo è in cima. Usiamo questo per confrontare i percorsi candidati con il peggio dei percorsi K '.