Qualcuno mi può dare una dritta e segnalarmi che errore faccio nell’implementazione dell’algoritmo di Dijkstra? (restando in C e non u altri linguaggi che purtroppo al momento non conosco e usando la matrice delle adiacenze e non la lista)
Grazie
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct {int costo; int definitivo;}Vertice;
int vertici;
int archi;
int grafo[10000][10000];
Vertice nodi[10000];
int sorgente;
int destinazione;
int min(int a, int b)
{
if(a>b)
return a;
else
return b;
}
void dijkstra()
{
int i;
for(i=0; i<vertici; i++)
{
nodi[i].costo=grafo[i][0];
}
int min=INT_MAX;
int pmin=0;
for(i=0; i<vertici; i++)
{
if(nodi[i].costo<min)
{
min=nodi[i].costo;
pmin=i;
}
}
int attuale=pmin;
while(!nodi[destinazione].definitivo)
{
for(i=0; i<vertici; i++)
if(!nodi[i].definitivo)
{
if(grafo[i][attuale]<min)
{
min=nodi[i].costo;
pmin=i;
}
}
nodi[pmin].definitivo=1;
nodi[pmin].costo=nodi[attuale].costo+grafo[pmin][attuale];
attuale=pmin;
}
printf("%d", nodi[i].costo);
}
main()
{
freopen("input.txt", "r", stdin);
freopen("oputput.txt", "w", stdout);
int i,j;
for(i=0; i<10000; i++)
{
nodi[i].costo=0;
nodi[i].definitivo=0;
for(j=0; j<10000; j++)
grafo[i][j]=0;
}
scanf("%d", &vertici);
scanf("%d", &archi);
scanf("%d", &sorgente);
scanf("%d", &destinazione);
for(i=0; i<archi; i++)
{
int sorgente, destinazione, peso;
scanf("%d%d%d", &sorgente, &destinazione, &peso);
grafo[sorgente][destinazione]=peso;
grafo[destinazione][sorgente]=peso;
}
}
Ciao, un’implementazione dell’algoritmo di Dijkstra per calcolare le shortest path in un grafo sparso (E \le O(V)) implica quanto meno l’utilizzo delle liste di adiacenza.
Se invece ti è sufficente una soluzione con complessità O(V^2), non hai bisogno di utilizzare né liste di adiacenza né heap come coda di priorità.
Per quanto riguarda la tua implementazione, una volta che hai determinato il nodo non ancora utilizzato con distanza minore, ti manca un ulteriore ciclo in cui cercare di migliorare/“rilassare” le distanze con gli archi uscenti dal nodo individuato.
EDIT: Anzi mi sembra che il tuo codice faccia qualcosa di diverso, prova a spiegarlo meglio o comunque a rileggere il funzionamento dell’algoritmo 
1 Mi Piace
Scusa se approfitto della tua disponibilità ma sono disperato…
Potresi chiarirmi meglio o (se hai voglia) scrivermi in che punto dell’algoritmo sbaglio?
Grazie mille
Mi spiegheresti un passo alla volta cosa fa il tuo algoritmo?
Comunque, ti conviene rappresentare il grafo con una lista di adiacenza e in C++ 
, concentrati su questo prima di passare all’algoritmo di Dijkstra, anche perché la versione asintoticamente più efficiente richiede l’utilizzo di una o più strutture dati che in C dovresti implementare ogni volta.
Detto questo, se spieghi meglio le idee dietro al tuo codice posso vedere se riesco ad aiutarti
2 Mi Piace
Provo a commentare con quello che nella mia idea dovrebbe fare il codice.
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct {int costo; int definitivo;}Vertice;
int vertici;
int archi;
int grafo[10000][10000];
Vertice nodi[10000];
int sorgente;
int destinazione;
int min(int a, int b)
{
if(a>b)
return a;
else
return b;
}
void dijkstra()
{
int i;
//all'inizio il costo è quello dal nodo di partenza al nodo selezionato
for(i=0; i<vertici; i++)
{
nodi[i].costo=grafo[i][0];
}
int min=INT_MAX;
int pmin=0;
//seleziono il nodo con costo minimo e lo rendo definitivo
for(i=0; i<vertici; i++)
{
if(nodi[i].costo<min)
{
min=nodi[i].costo;
pmin=i;
}
}
int attuale=pmin;
//ripeto la stessa operazione fino a quando il nodo destinazione non diventa definitivo
while(!nodi[destinazione].definitivo)
{
for(i=0; i<vertici; i++)
if(!nodi[i].definitivo)
{
if(grafo[i][attuale]<min)
{
min=nodi[i].costo;
pmin=i;
}
}
nodi[pmin].definitivo=1;
//aggiorno i costi dei nodi adiacenti nodi[pmin].costo=nodi[attuale].costo+grafo[pmin][attuale];
attuale=pmin;
}
printf("%d", nodi[i].costo);
}
main()
{
freopen("input.txt", "r", stdin);
freopen("oputput.txt", "w", stdout);
int i,j;
for(i=0; i<10000; i++)
{
nodi[i].costo=0;
nodi[i].definitivo=0;
for(j=0; j<10000; j++)
grafo[i][j]=0;
}
scanf("%d", &vertici);
scanf("%d", &archi);
scanf("%d", &sorgente);
scanf("%d", &destinazione);
for(i=0; i<archi; i++)
{
int sorgente, destinazione, peso;
scanf("%d%d%d", &sorgente, &destinazione, &peso);
grafo[sorgente][destinazione]=peso;
grafo[destinazione][sorgente]=peso;
}
}
Ho sviluppato questo algoritmo che prende in input una matrice 5x5 (quindi un grafo) contenente solo valori binari e che verrà scansionata N = 5 volte, nel frattempo si aggiorna il vettore dei costi che alla fine dell’algoritmo visualizzerà i percorsi minimi.
#include "../../std_lib_facilities.h"
using namespace std;
#define N 5
/*---------------------------------------------------------------------------------------------------
* algoritmo inizialmente sviluppato tramite matlab, poi successivamente
* riconvertito in vari linguaggi come Java,Python e C++.
* Super efficienza, chiarezza del codice, semplicità e portabilità.
* L'algoritmo prende come input una matrice 5x5 simmetrica e di adiacenza
* e la scansiona fino a N volte ai fini di calcolare la distanza tramite il vettore dei costi (cost);
* ---------------------------------------------------------------------------------------------------
*/
void load_matrix(int [][N]);
int main()
{
cout<<"------------------------------------------------------------"<<endl;
cout<<" Algorithm Edsger Wybe Dijkstra (minimal route : Graph) © ."<<endl;
cout<<"------------------------------------------------------------"<<endl;
cout<<" By Simone Remoli . "<<endl;
cout<<"------------------------------------------------------------"<<endl;
srand((unsigned int)time(NULL));
int mat_simmetrica[N][N]={0};
load_matrix(mat_simmetrica);
int cost[N],conosciuti[N];
for(int i=0;i<N;i++)
{
cost[i]=10000;
conosciuti[i]=0;
}
int min;
cost[0]=0;
conosciuti[0]=1;
int nodo_attuale = 0;
int c = 0;
for(int matrix_type = 0;matrix_type<N;matrix_type++)
{
for(int i=0;i<N;i++)
{
if((mat_simmetrica[i][nodo_attuale]!=0)&&((mat_simmetrica[i][nodo_attuale]+cost[nodo_attuale])<cost[i]))
cost[i] = (cost[nodo_attuale]+mat_simmetrica[i][nodo_attuale]);
}
min = 10000;
for(int i=0;i<N;i++)
{
if((cost[i]<min)&&(conosciuti[i]==0))
{
min = cost[i];
c = i;
}
}
conosciuti[c]=1;
nodo_attuale = c;
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<mat_simmetrica[i][j]<<"\t";
}
cout<<endl;
cout<<endl;
}
cout<<"------------------------------------------------------------"<<endl;
cout<<" conosciuti costi "<<endl;
for(int i=0;i<N;i++)
{
cout<<conosciuti[i]<<" - - - - - "<<cost[i]<<" "<<i+1<<endl;
}
keep_window_open();
}
void load_matrix(int mat_simmetrica[][N])
{
int mat[N][N];
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
mat[i][j]=rand()%2;
for(int i=0;i<N;i++)
mat[i][i]=0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
mat_simmetrica[j][i] = mat[i][j];
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
mat_simmetrica[i][j] = mat[i][j];
}
, concentrati su questo prima di passare all’algoritmo di Dijkstra, anche perché la versione asintoticamente più efficiente richiede l’utilizzo di una o più strutture dati che in C dovresti implementare ogni volta.