Dijkstra[O algoritmo está fazendo o caminho errado, como concertar?]

ademario71
(usa PCLinuxOS)

Enviado em 05/07/2015 - 15:00h

#include<stdio.h>
#include<stdlib.h>
#define INF 999

void dijkstra(int n,int v,int custo[10][10],int distancia[]){

int i, u, cont, w, visitado[10], min;

for(i= 1; i <= n; i++){
visitado[i]= 0; //Inicializando o vetor com todas as posições com zero
distancia[i]= custo[v][i];// Guardando os custos no vetor de distância
}
cont=2;
while(cont <= n){
min= INF;// Marcando como infinito
for(w= 1; w <= n; w++){
if(distancia[w] < min && !visitado[w]){
min= distancia[w];//Extraindo a distância minima
u= w;//Pegando a posição W
visitado[u]=1;//Se a posição U já foi visitada recebe valor 1
cont++;
for(w= 1; w <= n; w++){
if((distancia[u] + custo[u][w] < distancia[w]) && !visitado[w]){//verifica se a distancia + custo de um determinado vertice é menor que a distância de w e esse W não foi visitado
distancia[w]= distancia[u] + custo[u][w];// Se for verdade é adicionado a W a distancia nova que é a mínima
}
}
}
}
}
}


int main(){
int n, v, i, j, custo[10][10], distancia[10];

printf("\n ------- ALGORITMO DE DIJKSTRA ------ ");
printf("\n Digite a quantidade de nos:");
scanf("%d",&n);
printf("\n Digite a matriz de adjacencia: \n");

for(i= 1; i <= n; i++){//Percorrendo a matriz adjacente
for(j= 1; j <= n; j++){//Percorrendo a matriz adjacente
printf("Aresta entre < %d %d > PESO = ",i,j);//printando a ligação entre os verticeis(AS ARESTAS)
scanf("%d", &custo[i][j]);//Pegando o custo das arestas
if(custo[i][j] == 0){//Transformando os custos "0" em valores INFINITOS
custo[i][j] = INF;// Aresta na posição (i,j) recebe peso infinito
}
}
}

printf("\n Insira o vertice de origem:");
scanf("%d", &v);
dijkstra(n, v, custo, distancia);
printf("\n caminho mais curto:\n");

for(i= 1; i <= n; i++){
if(i!= v){
printf("%d->%d, custo=%d\n", v, i, distancia[i]);// Imprimindo a distancia da origem a o proximo vertice e o custo
}
}
}