[C++] Algoritmo di Dijkstra

[FinalFantasy]

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]

mi sn dimenticato di postare il grafo

[Sommovir]

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

SommoVir

[Sommovir]

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

[FinalFantasy]

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]

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

[FinalFantasy]

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]

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