PDA

Visualizza la versione completa : [C++] Algoritmo di Dijkstra e determinazione cammino minimo


Negan
13-05-2018, 14:36
Salve, mi aiutate con questo codice? In pratica dati dei nodi, costruisco la matrice di adiacenza e poi dato un nodo di partenza e uno di arrivo mi serve trovare il costo del cammino minimo e il percorso..Ma non funziona correttamente..ecco il codice:

#include <iostream>
#include <climits>
using namespace std;
int main()
{
int n,i,j,p;
char g,s;
cout<<"Quanti nodi? ";
cin>>n;
int matrice[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j) matrice[i][j]=0;
else
{
cout<<"Il nodo "<<i<<" e' collegato al nodo "<<j<<"?(s/n) ";
cin>>g;

if(g=='s' || g=='S')
{
cout<<"Inserisci peso: ";
cin>>p;
matrice[i][j]=p;
}
else if(g=='n' || g=='N')
{
matrice[i][j]=-1;
}
}
}
}
for(i=0;i<n;i++)
{
if(i==0) cout<<" ";
cout<<i<<" ";
}
cout<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j==0)
{
cout<<i<<" - | ";
}
if(matrice[i][j]==-1) cout<<"*| ";
else
{
cout<<matrice[i][j]<<"| ";
}
}
cout<<endl;
}

int D[n],Attuale,Min,Fine,Inizio; //vettore delle DISTANZE, variabile che contiene da dove si parte, percorso minimo, nodo di destinazione, nodo di partenza
for (i=0; i<n; i++) D[i] = INT_MAX;
int P[n]; // vettore che contiene i nodi di precedenza
for (i=0; i<n; i++) P[i] = -1;
int V[n]; // vettore dei VISITATI che contiene, per ciascun nodo,
// 0 se il nodo non è stato visitato, 1 altrimenti
for (i=0; i<n; i++) V[i] = 0;
cout<<"Inserisci nodo partenza: ";
cin>>Inizio;
cout<<"Inserisci nodo arrivo: ";
cin>>Fine;
D[Inizio] = 0;
Attuale=Inizio;
Min=0; // distanza minima dal nodo attuale
while ( Attuale!=Fine && Min!=INT_MAX) {
// si cerca il nodo più promettente, ossia quello con distanza minima
// che non sia ancora stato visitato
Min = INT_MAX;
for (i=0; i<n; i++)
if ( V[i] == 0 && D[i] < Min ){ Min = D[i]; Attuale = i; }
V[Attuale] = 1; //Attuale è il nodo scelto che poi non si elaborerà più
// aggiornamento vettori distanze (D) e provenienze (P)
for (i=0; i<n; i++)
if ( matrice[Attuale][i] != INT_MAX && D[i] > D[Attuale] + matrice[Attuale][i])
{ D[i] = D[Attuale] + matrice[Attuale][i]; P[i] = Attuale; }
}

/* stampa */
if ( V[Fine] == 0)
cout<<"NON esiste cammino da nodo "<<Inizio<<" a "<<Fine;
else { cout<<"cammino di peso "<<D[Fine];
i=Fine;
cout<<"\npercorso a ritroso ";
while (i!=Inizio) { cout<<i<<" "; i=P[i]; }
cout<<i<<" "; }
return 0;



}

astolfo96
13-05-2018, 14:58
sistema l'indentazione del codice mettendolo tra [ code ] [ / code ] (togli gli spazi dentro le quadre)

Negan
13-05-2018, 15:04
fatto :D

alka
15-05-2018, 11:30
Ma non funziona correttamente.. [...]


Ovvero cosa succede? Ottieni un errore? Un risultato sbagliato?
Aggiungi qualche dettaglio.

Negan
15-05-2018, 11:33
il "cammino di peso" risulta errato

Loading