come salvare il percorso più breve nell'algoritmo dijkstra

Question

Quindi, prima definiamo l'algoritmo Dijkstra:
L'algoritmo di Dijkstra trova percorsi più brevi a sorgente singola in un grafico orientato con pesi di bordo non negativi.
Desidero sapere come posso salvare la forma di percorso più breve da s a t con l'algoritmo Dijkstra.
Ho cercato su google, ma non ho trovato nulla di particolare; Ho anche modificato l'algoritmo di Dijkstra, ma non ho potuto ottenere alcuna risposta. Come posso salvare il percorso più breve da s a t con Dijkstra?
So che la mia domanda è semplice e poco professionale, ma qualsiasi aiuto sarebbe apprezzato. Grazie per aver considerato la mia domanda.

Answer 1

Se si guarda alla pseudocode dal link Wikipedia hai dato, si vedrà un array in là chiamato prev[]. Questa matrice contiene, per ciascun nodo v nel grafico, il nodo precedente u nel percorso più breve tra il nodo sorgente s e v. (. Questo vettore è chiamato anche predecessore o genitore array)

In altre parole, il percorso più breve tra s e v è:

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

Il percorso dal s a u potrebbe avere diversi nodi in mezzo, in modo da ricostruire il percorso da s a v, basta camminare indietro lungo il percorso definito dal prev[] array usando il frammento di codice sotto la pseudocodice principale (bersaglio è v):

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

La maggior parte delle librerie che utilizzano questo algoritmo probabilmente ti daranno un modo per farlo. Ma in generale, tieni traccia del percorso di ogni nodo. Vale a dire dare ad ogni nodo un attrribute shortestPathToNode in cui memorizzare l'elenco dei nodi

Answer 3

Un modo estremamente breve per farlo è quello di utilizzare la ricorsione e un "array principale". Se si inizializzano tutti i genitori dei punti su -1, e poi come si completa dijkstra, si aggiorna l'array genitore, si può ricorrere indietro da qualsiasi punto fino ad arrivare alla fonte e stampare il percorso. Ecco una breve e facile da capire ricorsione frammento:

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

Nota che invece di stampa "j" fuori, è possibile memorizzare in un vettore globale (o altro tipo di dati per le lingue che non sono C-correlati) per un uso successivo.