Algoritmo Dijkstra

[Brteo]

Ciao a tutti, sto cercando di implementare l'algoritmo di dijkstra per la ricarca del percorso minimo di un grafo da un nodo A ad uno B.
Prima cosa eseguo l'algorimo di dijkstra che trova la distanza dal nodo A a tutti i nodi del grafo (http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra). A questo punto per trovare il percorso minore dal nodo A a quello B risalgo il grafo al contrario ovvero dal nodo B all'A ma non riesco a trovare la tecnica giusta. Da come mi sembra di capire dai vari esempi che ho trovato, per risalire passo al nodo con potenziale tra i vari nodi che ho più alto. ESEMPIO dal nodo D(potenziale 13) che ha come adiacenti i nodi E e F, passo al nodo E(potenziale 9) anzichè al nodo F(potenziale 8).

Spero di essermi spiegato, se qualcuno ha già utilizzato questo algoritmo di potesse spiegare cosa sbaglio sarei contento :D

[nucce]

l'unica cosa che posso è dirti è di provare a guardare qui (http://cs.unibg.it/martigno/documenti/architetture/6-Routing.pdf) per vedere se capisci meglio

[Brteo]

Grazie nucce per l'informazione, il problema è che tutte le teorie che trovo su l'algoritmo di dijkstra, compresa la tua segnalazione, non mi spiega come trovare il percorso minimo tra due punti.

[funky80]

Allora, il nodo successivo della sequenza è sempre quello che:

1) è adiacente ad uno dei nodi già "attivi", cioè per cui ho già calcolato il potenziale
2) ha la somma del potenziale del nodo adiacente e del percorso minima.

da come ti sei spiegato sembra tu abbia capito esattamente il contrario di come funziona il tutto, se hai un nodo D con potenziale 13 e due nodi E e f con percorsi rispettivamente di 8 e 9 scegli quello a percorso minore ( cieè cerchi il cammino minimo !)

p.s quando, ad ogni iterazione, aggiorno le etichette con i potenziali e scelgo quello minore adiacente mi segno anche a che nodo appartiene. Questo vale anche per il nodo finale e quindi alla fine, partendo dal nodo finale, sò esattamente passo passo all'indietro come muovermi

[Brteo]

Grazie delle risposte, sono riuscito a far funzionare mantenendomi memorizzato il predecessore di ogni nodo durante l'esecuzione dell'algoritmo. Così facendo ho semplicemente risalito i predecessori dal nodo di arrivo.

da come ti sei spiegato sembra tu abbia capito esattamente il contrario di come funziona il tutto, se hai un nodo D con potenziale 13 e due nodi E e f con percorsi rispettivamente di 8 e 9 scegli quello a percorso minore ( cieè cerchi il cammino minimo !)

il motivo per cui sceglievo di passare al nodo con potenziale più alto era perchè significava che la distanza tra i due era minore, funzionava ma non in tutti i casi e quindi mi ero intestardito con un metodo da me inventato non del tutto funzionante :D

Grazie dell'aiuto