PDA

Visualizza la versione completa : [C++] Algoritmo di Dijkstra


FinalFantasy
11-11-2005, 23:59
void Grafo::Dijkstra(int start)
{
bool *v;
float m,*d;
int i,j,*p;

v = new bool[n_nodi];
d = new float[n_nodi];
p = new int[n_nodi];

for (int i=0;i<n_nodi;i++)
{
d[i]=INFINITO;
v[i]=false;
p[i]=-1;
}

d[start]=0;

do
{
m=INFINITO;

for (i=0;i<n_nodi;i++)
{
if (v[i]==false)
{
if (d[i]<m)
{
m=d[i];
j=i;
}
}
}

if (m!=INFINITO)
{
v[j]=true;
}

for (i=0;i<n_nodi;i++)
{
if (ListaAdiacenza[j][i]!= INFINITO)
{
if (d[i]>(d[j]+ListaAdiacenza[j][i]))
{
d[i]=d[j]+ListaAdiacenza[j][i];
p[i]=j;
}
}
}
}
while (m!=INFINITO);

}



questo la versione codificata dell'algoritmo di dijkstra, cio l'algoritmo che permette di calcolare il percorso minimo tra un nodo sorgente visitando tutti gli altri nodi facendo quanta meno strada possibile...

Ora, funziona a modo suo. Ho trovato a spasso x la rete questo grafo (allegato al thread) di cui fatto a carta e penna (e verificato sul sito in cui lo trovato) il percorso minimo

0->3->1->2


Xo il codice ke vi ho dato mi da un'altro risultato

0->3->1

Visitando il nodo 2 a parte, facendo 0->2. Cio la sorgente prende due strade...why???xke????

FinalFantasy
12-11-2005, 00:03
mi sn dimenticato di postare il grafo

Sommovir
12-11-2005, 17:41
ciao final, beh nn ho tempo di analizzare il codice in dettaglio.. scusami.. (devo scappare) ma a prima vista penso ke vada tutto ok.. forse da l'ultimo nodo x scontato.. cio ti da il cammino fino al penultimo nodo.. x sai mi suona strana una cosa.. il dijkstra restituisce non il cammino minimo dalla sorgente ad un nodo in particolere.. ma proprio l'MST... quindi cmq dovrebbe beccarlo cmq quel vertice.. poi certo ke la sorgente prende 2 strade.. questo algoritmo un Greedy, quindi deve provare tutte le possibile strade e poi con una scelta greedy prende quella con costo minore.. anzi nel dettaglio all'inizio parte dal vertice e testa tutti gli archi uscenti e mette nella soluzione quello di peso minimo.. poi parte da quel vertice e fa la stessa cosa ma ai nuovi pesi degli archi ci somma il peso dell arco di prima scelto! e cos via.. poi vabb saprai ke i pesi devono essere tutti positivi.. vedo ke il grafo rappresentato x matrice di adiacenza.. magari se mi posti esattamente come fatta la classe grafo.. faccio un po' di test.. e ti dico meglio!! mo scappo, se nn sono stato chiaro dimmi !!

Algoritmi 1 e 2 me so piaciuti troppo ! li stai studiando anke te ?

ciao ciao :ciauz:

SommoVir

Sommovir
12-11-2005, 17:45
ehm scusa sono stato scorretto.... ma lo anke la figura....

ti ho parlato di MST.. ma xk ho visto il grafo ke non orientato, inveec il dikstra lavora SOLO su grafi ORIENTATI, x il grafo come quello in figura il top Kruskal o il mio preferito Prim x anke se non orientato te lo restituisce cmq un MST (anke se di solito x mst si intende un albero NON orientato) quindi nella soluzione l'arco 0-2 ci deve essere sempre ke il verso dell'arco del grafo sia concorde.. beh giustamente il percorso minimo x arrivare a 2 partendo da 0... !!

CIAO CIAOoouuuu :ciauz: :)

FinalFantasy
12-11-2005, 22:13
Beh...nn sn daccordo sul fatto che lavora solo su grafi orientati, perch mettiamo il caso che io abbia un grafo orientato di cui ogni nodo collegato a tutti altri nodi, quindi ci sar un l'arco che va da A->B con peso 2 e un'altro arco B->A con peso 2...Io i grafi non orientati li tratto come grafi orientati che vanno a X->Y e Y->X

nn vedo la differenza.

Sommovir
13-11-2005, 14:29
se dici in quel modo certo ke funziona... ma usi una matrice piena simmetrica... sprechi un po' l'algoritmo.. a quel punto usa un Kruskal.. ke in nlogn ti risolve tutto :fighet: x grafo xk il dikstra ogni volta considera pure l'arco di ritorno.. tra 2 vertici.. ma poi nn lo prende mai xk nn gli conviene... gli archi hanno peso positivo x l'istanza del problema, cmq ho fatto la prova a mano sul tuo grafo, e mi funziona l'algo, te come fai a farti stampare la soluzione ? magari c' un errore nella procedura di visualizzazione, inoltre mi veniva un albero... ti do il vettore dei padri ke mi venuto a me:

0 1 2 3
- 3 0 0

0 la radice e la riga sopra sono i vertici, e sotto ogni vertice c' il padre

:ciauz:

FinalFantasy
13-11-2005, 15:36
A me, quel grafo viene. 0 3 1 2

L'algoritmo di dijsktra mi biforca la radice, cio 0 me lo fa andare sia a 3 sia a 2...infatti viene

0->3->1

Io nn capisco perch quando va a 1 nn si sposta a 2 visto che l'ultimo nodo da visitare....

Sommovir
13-11-2005, 18:34
ma va bene ke si biforca.. il dijkstra funzia ke prima prende tutti i nodi uscenti dalla sorgente e mette i pesi in d[u] quindi al primo passo da 0 prende in considerazione sia il 3 ke il 2 e poi continua sull'arco di peso minimo.. quindi il 3.. e poi itera lo stesso procedimento su quel vertice sommando il peso degli archi uscenti dal nodo corrente al peso ke costava andare dalla radice al nodo corrente, quindi sceglie con scelta Greedy (golosa) il percorso ottimale.. con il dijkstra non ottieni un solo cammino ma un "albero dei cammini minimi",... nn lo chiamo albero di copertura xk un altra cosa quella... (prim & Kruskal) vuol dire ke l'algoritmo di Dijkstra ti restituisce il cammino di peso minimo x andare dalla Sorgente ad ogni nodo del grafo.. infatti x andare a 2 da 0 conviene andarci direttamente.. oki ? spero di essere stato chiaro.. se no ti posto uno svolgimento passo passo!

fammi sapere :ciauz:

Loading