Modifica dell'algoritmo di Dijkstra per ottenere il percorso più breve tra due nodi

Question

Quindi ho visto domande simili a questo, ma non esattamente esattamente quello che sto cercando. Devo modificare l'algoritmo di Dijkstra per restituire il percorso più breve tra un vertice S (sorgente) e un vertice X (destinazione). Penso di aver capito cosa fare, ma mi piacerebbe un aiuto. Ecco lo pseudocodice che ho modificato.

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]; 

Il codice è stata presa da Wikipedia e modificato: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Questo sembra corretta?

Answer 1

Non è necessario modificare l'algoritmo di Dijkstra, è un algoritmo di percorso più breve per tutte le coppie. Sembra che tu stia cercando di trovare il percorso più breve tra due nodi specifici: Dijkstra gestisce questa multa.

Se si desidera qualcosa progettato specificamente per un grafico non ponderato e non orientato, che è quello che sembra si stia facendo, suggerirei di fare un BFS.

Answer 2

Dopo aver trovato il percorso più breve a partire dal singolo SOURCE, è necessario iniziare con DESTINATION per tornare indietro al suo predecessore, in modo da stampare il percorso.

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; 
    } 
} 

codici sopra cortesia Introduzione alle Algorithm, MIT Press

Answer 3

Il modo migliore per affrontare questo è pensare in termini di percorsi da ciascun nodo raggiungibile indietro alla sorgente, comunemente indicato con v. Come aggiorna la distanza di ciascun dato nodo, tieni traccia del suo successore diretto su quel percorso a v. Tale nodo è il genitore del nodo dato nell'albero a distanza ravvicinata. Quando hai creato quella mappa genitrice, per trovare il percorso più breve da v a w, crea il percorso in ordine inverso: w, genitore [w], genitore [genitore [w]], ...