Zmodyfikuj algorytm Dijkstry, aby uzyskać najkrótszą ścieżkę między dwoma węzłami.

Question

Widziałem podobne pytania, ale nie do końca to, czego szukam. Potrzebuję zmodyfikować algorytm Dijkstry, aby zwrócić najkrótszą ścieżkę między wierzchołkiem S (źródło) i wierzchołkiem X (miejsce docelowe). Chyba wiem, co mam zrobić, ale chciałbym pomóc. Oto zmodyfikowany pseudokod.

1 function Dijkstra(Graph, source, destination): 
2  for each vertex v in Graph:        // Initializations 
3   dist[v] := infinity ;         // Unknown distance function from 
4                 // source to v 
5   previous[v] := undefined ;        // Previous node in optimal path 
6  end for             // from source 
7  
8  dist[source] := 0 ;          // Distance from source to source 
9  Q := the set of all nodes in Graph ;      // All nodes in the graph are 
10                 // unoptimized - thus are in Q 
11  while Q is not empty:          // The main loop 
12   u := vertex in Q with smallest distance in dist[] ; // Start node in first case 
13   remove u from Q ; 
14   if dist[u] = infinity: 
15    break ;           // all remaining vertices are 
16   end if             // inaccessible from source 
17   
18   for each neighbor v of u:        // where v has not yet been 
19                 // removed from Q. 
20    alt := dist[u] + dist_between(u, v) ; 
21    if alt < dist[v]:         // Relax (u,v,a) 
22     dist[v] := alt ; 
23     previous[v] := u ; 
24     decrease-key v in Q;       // Reorder v in the Queue 
25    end if 
26   end for 
27  end while 
28 return dist[destination]; 

Kod został zaczerpnięty z Wikipedii i modyfikowany: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Czy to wygląda prawidłowa?

Answer 1

Algorytm Dijkstry nie musi być modyfikowany, jest algorytmem najkrótszej ścieżki dla wszystkich par. Wygląda na to, że próbujesz znaleźć najkrótszą ścieżkę między dwoma konkretnymi węzłami - Dijkstra obsługuje tę grzywnę.

Jeśli chcesz coś, co zostało zaprojektowane specjalnie dla nieważonego, nieukierunkowanego wykresu, który wydaje Ci się, że robisz, sugerowałbym wykonanie BFS.

Answer 2

Po znalezieniu najkrótszej ścieżki, zaczynając od pojedynczego SOURCE, musimy rozpocząć od DESTINATION, aby cofnąć poprzednią ścieżkę, aby wydrukować ścieżkę.

Print-Path(G,s,v) 
{ 
    if(v==s) 
     print s; 
    else if (pi[v]==NULL)  
     print "no path from "+s+" to "+v; 
    else{ 
     Print-Path(G,s,pi[v]) 
     print v; 
    } 
} 

kody Powyższe uprzejmości wprowadzeniem do algorytmu MIT Press

Answer 3

Najlepszym sposobem podejścia jest to, aby myśleć w kategoriach ścieżek z każdego osiągalnego węzła z powrotem do źródła, zwykle oznaczony przez v. Jak Ciebie aktualizuje dystans każdego węzła, śledząc jego następcę bezpośredniego na tej ścieżce do v. Węzeł ten jest rodzica danego węzła w drzewie najkrótszej odległości do v. Po zbudowaniu mapy nadrzędnej, aby znaleźć najkrótszą ścieżkę od v do w, zbuduj ścieżkę w odwrotnej kolejności: w, rodzic [w], rodzic [rodzic [w]], ...