Hatasız grafikte KSPA için öneriler

Question

Yeniden yazılması gereken özel bir KSPA uygulaması var. Mevcut uygulama, pseudocode kabaca aşağıda açıklandığı gibi değiştirilmiş bir Dijkstra'nın algoritmasını kullanmaktadır. Öyle sanırım kenar silme stratejisini kullanarak KSPA olarak bilinir. (Ben grafik teorisinde bir acemiyim). i algoritması anlamak gibi

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 

, 'k-1' SPTs her kaynak-hedef çifti ve 'k-1' arasında bulunan edilecek, k'ıncı kısa yolu elde etmek için bir SPT her silinecekse kenarları her kombinasyon için eşzamanlı olarak. Açıkça bu algoritmanın kombinatoryal karmaşıklığı vardır ve sunucuyu büyük grafiklerde tıkar. İnsanlar bana Eppstein'ın algoritmasını önerdi (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf). Ama bu beyaz kağıt bir 'digraph' yazıyor ve ben sadece digraphlar için çalıştığını söylemedim. Bu algoritmayı doğrulanmamış bir grafikte kullanan biri varsa, buraya sadece buraya sormak istedim. Olumlu bir grafikte KSPA'yı uygulamak için iyi algoritmalar (zaman-karmaşıklık açısından) var mı? peşin

sayesinde

Answer 1

Zaman karmaşıklığı: O (K * (E * log (K) + V * log (V))) O (K * V)

Bellek karmaşıklığı (+ Girişi kaydetmek için O (E). Her bir düğüm için

• yerine başlangıç ​​düğümden güzergahın en anda bilinen maliyet tutmanın aşağıdaki gibidir:

  Bir tadil edilmiş Djikstra gerçekleştirin.

• Başlangıç ​​düğümünden en iyi K rotalarını tutuyoruz Bir düğümün komşularını güncellerken, en iyi bilinen yolu (Djikstra gibi) geliştirip geliştirmediğini kontrol etmiyoruz, K 'nin en kötüsünü en kötü şekilde iyileştirip iyileştirmediğini kontrol ediyoruz. şu anda bilinen yol.
• Daha önce düğümlerin en iyi yollarından birisini işledikten sonra, K en iyi rotalarını bulmamız gerekmiyor, ancak yalnızca K-1 kalan ve diğer bir K-2'den sonra. Ben K 'dediğim şey bu.
• Her düğüm için, K'nın en iyi bilinen yol uzunlukları için iki öncelikli kuyruk tutacağız.
  • Bir öncelik sırasına göre en kısa yol üstte. Bu öncelik sırasını, K 'nin hangisinin en iyisi olduğunu belirlemek ve düğümün temsilcisi olarak düzenli Djikstra'nın öncelik sıralarında kullanacağız.
  • Diğer öncelik sırasındaki en uzun yol üstte. Bunu aday yollarını K 'yollarının en kötüsüyle karşılaştırmak için kullanırız.