dijkstra algoritmasında en kısa yol nasıl kaydedilir

Question

Öncelikle Dijkstra algoritmasını tanımlayalım:
Dijkstra'nın algoritması, negatif olmayan kenar ağırlıklarına sahip yönlendirilmiş bir grafikte tek kaynak en kısa yolları bulur.
Dijkstra algoritması ile en kısa yol formunu t'ye nasıl kaydedebilirim bilmek istiyorum.
Google'da arama yaptım, ancak özel bir şey bulamadım; Ayrıca Dijkstra algoritmasını da değiştirdim, ama herhangi bir cevap alamadım. Dijkstra ile s arasındaki en kısa yolu nasıl kaydedebilirim?
Sorunun temel ve profesyonelce olmadığını biliyorum, ancak herhangi bir yardım takdir edilecektir. Sorumu düşündüğün için teşekkürler.

Answer 1

listesini depolamak her bir düğüme bir attrribute shortestPathToNode ver. Bu dizi, her bir düğümde grafikte v için, önceki düğümü kaynak düğüm s ve v arasındaki en kısa yolu u içerir. (. Bu dizi de önceki veya üst dizi olarak adlandırılır), diğer bir deyişle

, s ve v arasındaki en kısa yolu: s ile

s -> u -> v 
where u = prev[v] 

yolu - to, aralarında birkaç düğüm olabilir, bu nedenle s - yolunu yeniden oluşturmak için v, sadece ana yalancı kod aşağıdaki kod parçacığını kullanarak prev[] dizisi tarafından tanımlanan yol boyunca geri yürümek (hedefev olan): bunu

1 S ← empty sequence 
2 u ← target 
3 while prev[u] is defined:     // Construct the shortest path with a stack S 
4  insert u at the beginning of S   // Push the vertex onto the stack 
5  u ← prev[u]        // Traverse from target to source 
6 end while 

Answer 2

Bu algoritmayı kullanan çoğu kitaplık, bunu yapmanın bir yolunu gösterecektir. Ancak genel olarak her bir düğüme giden yolu takip edin. Yani hangi size verdi Vikipedi bağlantısından pseudocode bakarsak, sen prev[] denilen orada bir dizi göreceksiniz düğümler

Answer 3

Bir son derece kısa yolu Özyinelemeyi kullanmaktır ve bir "ana dizi". Tüm noktaların ebeveynlerini -1 olarak başlatırsanız ve daha sonra dijkstra'ları tamamladıktan sonra ana diziyi güncellerseniz, kaynağa ulaşıncaya ve yolu yazdırıncaya kadar herhangi bir noktadan geri dönebilirsiniz. (Bu C ilişkisi olmadığını diller için veya başka bir veri türü) yerine dışarı baskı "j", bir küresel vektör içinde saklayabilirsiniz

// Function to print shortest path from source to j using parent array 
void path(parent array, int j) 
{ 
    // Base Case : If j is source 
    if (jth element of parent is -1) return; 
  
    path(parent, jth element of parent); 
  print j; 
} 

Not: Burada tekrarlama pasajını anlamak için çok kısa ve kolay Daha sonra kullanmak için.