[C++] Algorimo di Dijkstra

[lucia983]

Salve a tutti..

sono una studentessa alle prime armi con il C++ e devo implementare l'algoritmo d Dijkstra.. mi chiedevo se qualcuno ha dei consigli per me.. vi ringrazio!

[king64]

Guarda qui . Anche questo link ti può essere utile . Ciao

[lucia983]

rinnovo la mia richiesta per ulteriori consigli.. ringrazio tutti!

[lucia983]

Ho implementato in c++ un algoritmo per svolgere Dijkstra.. il problema è che riesco a farmi dare tutte le distanze dalla sorgente.. ma non riesco a fargli visitare l'albero dei cammini minimi.. avete qualche suggerimento!? devo implementare una nuova vlasse per fare la visita?

[cshark]

Potresti postare il sorgente, per favore?

[murder eyes]

Se utilizzi il vettore dei padri e ti crei così il cammino? Da questo non è così complicato costruirsi l'albero no?

[lucia983]

Il sito di riferimento per la sorgente è questo.. ALGORITMO

lo cercate tra i cammini minimi di un grafo orientato..

io l'ho leggermente modificato perchè mi serviva solo dijkstra e di fare altre operazioni dopo aver trovato i cammini minimi..

ho sfruttato quelle librerie ma la visita dell'albero non funziona, e non riesco a venirne a capo.. perciò cercavo un modo alternativo per poter visitare l'albero_dijkstra.

L'algoritmo di Dijkstra che ho trovato in queste librerie restituisce l'albero dei cammini minimi in un oggetto di tipo Albero<vertice*> passato come parametro per riferimento, solo che compilando mi dice di non trovare il percorso.

[alka]

Ho unito le discussioni relative all'algoritmo per non creare meno dispersione delle informazioni.

[lucia983]

Sempre nel problema relativo all'algoritmo di dijkstra.. nel file albero.h ho trovato queste righe che non mi so spiegare.. sapete aiutarmi?

nodo<Chiave>* padre(nodo<Chiave>* v = 0) const;
nodo<Chiave>* figli(nodo<Chiave>* v) const;

[FinalFantasy]

Algoritmo di Dijsktra

N -> Numero dei nodi
Distanza() -> Vettore che contiene le distanze minime
Nodo_Visitato() -> Vettore che contiene la lista dei nodi visitati
Lista_Nodi_Precedenti() -> Vettore che contiene la lista dei nodi precedenti
S -> Nodo di partenza
G()() -> Grafo orientato

Per i da 0 a N
  Distanza(i) = INFINITO   
  Nodo_Visitato(i) =  Falso
  Lista_Nodi_Precedenti(i) =  -1

Distanza(S) = 0

Fai
  B = INFINITO

  Per i da 0 a N
    Se Nodo_Visitato (i) = Falso
      Se Distanza(i) < B
        B =  Distanza(i)
        j = i

  Se B ≠ INFINITO  
    Nodo_Visitato (j) = Vero

  Per i da 0 a N
    Se esiste l’arco G(j)(i)
      Se Distanza(i) > [Distanza(j) + G(j)(i)]
        Distanza(i) =  Distanza(j) + G(j)(i)
        Lista_Nodi_Precedenti(i) =  j
Mentre B ≠ INFINITO

prova a codificare questo...