Boa sexta pessoal!
Estou tentando fazer um algoritmo de dijkstra e não consigo entender o que pode estar dando de errado (postei o código inteiro por não saber se algo feito antes pode ter influenciado)
Funciona assim:
O programa deve ler um dados.txt que irá conter as características do meu grafo e montar uma matriz custo.
Na primeira linha o número de vértices, nas outras com V enumera os vértices,
A | ORIGEM | DESTINO | CUSTO.
F = nó fonte (raiz)
D = nó destino (final)
6
V 0
V 1
V 2
V 3
V 4
V 5
A 0 1 4
A 0 2 2
A 1 2 1
A 1 3 5
A 2 3 8
A 2 4 10
A 3 4 2
A 3 5 6
A 4 5 2
F 0
D 5
O problema acontece bem no final, quando tento botar um k++ para fazer o while funcionar. Alguém consegue explicar?
Também tive um problema com o custoTotal que precisei transformar em vetor para funcionar, não tenho a mínima ideia do porquê.
Agradeço a paciência de vocês.
#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>
using namespace std;
void preenche(int N, float** matriz)
{
for (int i=; i<N; i++)
{
for (int j=; j<N; j++)
{
matriz[i][j]=99999;
}
}
}
void mostra(int N, float **matriz)
{
cout<< "Matriz custo:"<< endl;
for (int i=; i<N; i++)
{
for (int j=; j<N; j++)
{
cout<<matriz[i][j]<<" ";
}
cout<< endl;
}
}
int main()
{
int n, de, para, od[2];
string linha;
char aux[100], *token, **nulo;
float **matriz, custo;
ifstream entrada("dados.txt");
if (entrada.is_open())
{
//recebe o número de vertices
entrada >>aux;
token = strtok(aux," ");
n = strtof(token, nulo);
//cria a matriz
matriz=new float*[n];
for (int i=; i<=n; i++)
matriz[i] = new float[n];
//Preenche a matriz
preenche(n, matriz);
//Faz a leitura do TXT completo e cria a matriz custo
while (!entrada.eof())
{
getline(entrada, linha);
strcpy(aux, linha.c_str());
token = strtok(aux," ");
if((token!= NULL) && (strlen(token)>=1))
{
//leitura das características de cada aresta
if(token[]=='A')
{
cout<< "ARESTA:" << endl;
token = strtok(NULL, " ");
de = strtof(token, nulo);
cout << "origem: "<<de<< endl;
token = strtok(NULL, " ");
para = strtof(token, nulo);
cout << "destino: "<<para<< endl;
token = strtok(NULL, " ");
custo = strtof(token, nulo);
cout << "custo: "<<custo<< endl;
matriz[de][para]=custo;
// matriz[para][de]=custo;
cout<< endl;
}
if(token[]=='F')
{
token = strtok(NULL, " ");
od[] = strtof(token, nulo);
cout << "Inicia em: "<<od[]<< endl;
}
if(token[]=='D')
{
token = strtok(NULL, " ");
od[1] = strtof(token, nulo);
cout << "Termina em: "<<od[1]<< endl;
cout<< endl;
}
}
}
}
else
cout << "ARQUIVO DE ENTRADA não ENCONTRADO!" << endl;
/// Algoritmo de Dijkstra
int c, i, j,k, l, rota[10], noaux;
float menor=9999, custoTotal[1];
//Primeiro vertice
k=;
rota[k]=od[];
k++; //k=1
for(j=; j<n; j++)
{
if(matriz[rota[k-1]][j] < menor)
{
menor = matriz[rota[k-1]][j];
rota[k]=j;
custoTotal[] = matriz[rota[k-1]][j];
}
}
k++; //k=2
cout<< "ROTA:"<< endl;
cout << rota[]<<endl;
cout << rota[1]<<endl;
//Próximos vértices
while(rota[k-1] != od[1])
{
menor=9999;
for(j=; j<n; j++)
{
c=;
if(matriz[rota[k-1]][j] < menor)
{
//checa se o vertice já foi visitado
for(l=; l<k; l++)
{
if(rota[l]==j)
c++;
}
if(c==)
{
menor = matriz[rota[k-1]][j];
rota[k]=j;
}
}
}
custoTotal[] = custoTotal[] + matriz[rota[k]-1][rota[k]];
///ESTRAGADOR--> k++;
}
//Mostra a matriz custo
mostra(n, matriz);
return ;
}