Suggerimenti per KSPA sul grafico indiretto

Question

Esiste un'implementazione personalizzata di KSPA che deve essere riscritta. L'attuale implementazione utilizza un algoritmo di Dijkstra modificato il cui pseudocodice è spiegato più o meno in seguito. È comunemente noto come KSPA che utilizza la strategia di eliminazione degli edge, credo. (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 ho capito l'algoritmo, per ottenere k-esimo cammino minimo, TSS 'k-1' si trovano tra ogni coppia sorgente-destinazione e 'k-1' bordi ciascuno da uno SPT sono da cancellare simultaneamente per ogni combinazione. Chiaramente questo algoritmo ha complessità combinatoria e blocca il server su grafici di grandi dimensioni. Le persone mi hanno suggerito l'algoritmo di Eppstein (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf). Ma questo libro bianco cita un 'digrafo' e non ho visto una menzione che funzioni solo per digrammi. Volevo solo chiedere alla gente qui se qualcuno ha usato questo algoritmo su un grafo non orientato?

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

Grazie in anticipo,

Answer 1

Tempo complessità: O (K * (E * log (K) + V * log (V)))

Memoria complessità O (K * V) (+ O (E) per memorizzare l'ingresso).

eseguiamo una Djikstra modificata come segue:

• Per ciascun nodo, invece di mantenere il miglior rapporto costo attualmente noto di percorso dall'inizio nodi. Manteniamo le migliori rotte K dal nodo iniziale
• Quando aggiorniamo i vicini di un nodo, non controlliamo se migliora il percorso attualmente più conosciuto (come fa Djikstra), controlliamo se migliora il peggio del K 'migliore percorso attualmente conosciuto.
• Dopo aver già elaborato il primo dei migliori percorsi K di un nodo, non abbiamo bisogno di trovare i percorsi migliori di K, ma solo di rimanere K-1 e dopo un altro K-2. Questo è quello che ho chiamato K '.
• Per ogni nodo manterremo due code di priorità per le migliori lunghezze del percorso attualmente conosciute di K.
  • In una coda di priorità il percorso più breve è in primo piano. Utilizziamo questa coda di priorità per determinare quale delle K 'è la migliore e verrà utilizzata nelle code di priorità regolari di Djikstra come rappresentante del nodo.
  • Nell'altra coda di priorità il percorso più lungo è in primo piano. Usiamo questo per confrontare i percorsi candidati al peggiore dei percorsi K '.