DIJKSTRA!!!!
Estoy trabajando en un proyecto el entrega la ruta más corta de un nodo a otro dentro de un grafo
Este grafo lo tengo representado como una matriz de costos
He trabajado en ello y lo tengo "RELATIVAMENTE RESUELTO"
Lo que sucede es que me genera una ruta corta aunado a las aristas consiguientes
Por ejemplo si to quiero ir del nodo A al B...
A-------3-------B
| |
2 5
| |
C-------9-------D
La ruta sería A->B pero el programa toma A->C->D->B, esto porque la arista de A->C es menor que la de A->B
Como puedo resolver este problema????
Y si alguien lo tiene, me podría proporcionar un codigo usando el algoritmo de Dijkstra???
Añado mi codigo a mi publicación para que lo puedan observar y me puedan auxiliar en esto
En verdad me urge tener este codigo, de antemano muchas gracias y excelente dia c:
PD: SUELO TENER ALGO DE CODIGO BASURA EN MIS PROYECTOS POR SI ENCUENTRAN ALGO QUE NO SE OCUPE PARA NADA, ES UN MAL HABITO QUE TENGO Y SIGO TRABAJANDO EN ELLO :'c#include<stdio.h>
#include<conio.h>
#define max 6
#define INFINITO 999999
/*
--------------- SABADO 2 DE JUNIO 2018
*************** PROGRAMA: 0206
*************** AXEL RODRIGUEZ
*************** METRO1 \ ESTRUCTURA DE DATOS
*/
int Menor(int distancia[max],int n, int visita_bandera[max])
{ int menor = INFINITO;
int i;
for (i=0;i<max;i++)
{
if ( (distancia[i] ) < menor )
{
menor = distancia[i];
}
}
return menor;
}
void Dijkstra (int matriz[max][max], int nodo_inicial, int nodo_final)
{
int i,j;
int auxiliar[max][max];
int distancia[max]={'\0'}; //VECTOR DONDE ESTARAN LAS DISTANCIAS GUARDADAS
int analisis[max]={'\0'}; //VECTOR DE FILA QUE SE VA A ANALIZAR
int visita[max]={'\0'}; //VECTOR EN EL QUE SE GUARDARAN LOS NODOS YA VISITADOS
int visita_bandera[max]={'\0'};
int z=1;
for (i=0 ; i<max ; i++) //DONDE NO EXISTA ADYACENCIA, LO MANDAMOS A UN VALOR MUUUUY ALTO PARA QUE NO SEA UTILIZADA
{ //UTILIZAMOS UNA //VECTOR EN EL QUE SE GUARDARAN LOS NODOS YA VISITADOS
for (j=0 ; j<max ; j++)
{
if (matriz[i][j] == 0)
{
auxiliar[i][j] = 999;
}
else{
auxiliar[i][j] = matriz[i][j];
}
}
}
distancia[0]=0;
visita[0]=nodo_inicial;
visita_bandera[nodo_inicial]=1;
do{
rutina:
for(i=0 ; i<max ; i++)
{
analisis[i] = auxiliar [nodo_inicial][i]; //GUARDAMOS EN ANALISIS[] LA FILA COMPLETA DONDE ESTE EL NODO INICIAL
}
int menor_analisis;
menor_analisis = Menor (analisis, 6, visita_bandera); //SE HACE USO DE LA FUNCION MENOR, ENVIANDOLE DE PARAMETROS EL VECTOR A ANALIZAR Y EL NUMERO
//DE ELEMENTOS DEL MISMO
int vist,reaccion; // EN VIST SE GUARDARA EL NODO VISITADO Y REACCION ES UNA BANDERA LA CUAL SERVIRA PARA DECIRNOS SI EL NODO YA FUE VISITADO
for(i=0 ; i<max ; i++) // O NO Y DE ESTE MODO EVITAR LOS BUCLES INFINITOS
{
if (menor_analisis == auxiliar[nodo_inicial][i])
{ // ENCUENTRA EL ELEMENTO EN LA MATRIZ DONDE ESTE EL DATO MENOR Y LA GUARDA EN VIST
vist = i;
break;
}
}
for(i=0 ; i<max ; i++) // O NO Y DE ESTE MODO EVITAR LOS BUCLES INFINITOS
{
if (menor_analisis == auxiliar[nodo_inicial][i])
{ // ENCUENTRA EL ELEMENTO EN LA MATRIZ DONDE ESTE EL DATO MENOR Y LA GUARDA EN VIST
vist = i;
}
}
for (i=0 ; i<max ; i++)
{
if (vist == visita[i])
{
reaccion=19;
}
else{
reaccion=0; // SI EL NODO NO HA SIDO VISITADO, REACCION ES 0, Y ESTOS NODOS SE MANDAN A INFINITO PARA QUE NO SE PUEDAN UTILIZAR
auxiliar[nodo_inicial][vist]=INFINITO;
auxiliar[vist][nodo_inicial]=INFINITO;
}
}
if(reaccion ==19)
{
auxiliar[vist][nodo_inicial]=INFINITO;
auxiliar[nodo_inicial][vist]=INFINITO;
goto rutina;
}
distancia[z]=menor_analisis; // SE GUARDA EN DISTANCIA LA ARISTA DE MENOR TAMAÑO
visita[z]=vist; // SE GUARDA EN VISITA EL NODO YA VISITADO
nodo_inicial = visita[z]; // SE IGUALA NODO INICIAL CON EL NODO ULTIMO VISITADO PARA QUE, CUANDO SE HAYA VISITADO
z++; // EL NODO_FINAL, SE DETENGAN LAS ITERACIONES
} while (nodo_inicial!=nodo_final);
printf(" RUTA A SEGUIR ---> "); for (j=0 ; j<6 ; j++)
{
if (visita[j] == nodo_final)
{
break;
}
}
int sumatoria=0;
for (j=0;j<6;j++)
{
sumatoria=sumatoria+distancia[j];
}
printf("DISTANCIA RECORRIDA --> %d", sumatoria
);
}
int main(){
int i,j; // j-> fila i-> columna
//int matriz[5][5];
int matriz [6][6]= { 0,4,2,0,0,0,
4,0,1,5,0,0,
2,1,0,8,9,0,
0,5,8,0,2,6,
0,0,9,2,0,2,
0,0,0,6,2,0}; //ESTA MATRIZ ES EL GRAFO, EN ESENCIA ESTARIA DE ESTE MODO
/*
NODO 2 --- 5 ----NODO 4
/ | / | \
4 | / | \
/ | / | \
NODO 1 1 8 2 NODO 6
\ | / | /
2 | / | /
\ |/ | /
NODO 3 ----9----- NODO 5 */
int auxiliar[6][6];
int distancia[6]={'\0'}; //VECTOR DONDE ESTARAN LAS DISTANCIAS GUARDADAS
int analisis[6]={'\0'}; //VECTOR DE FILA QUE SE VA A ANALIZAR
int visita[6]={'\0'}; //VECTOR EN EL QUE SE GUARDARAN LOS NODOS YA VISITADOS
for (i=0; i<6 ; i++)
{
for (j=0; j<6; j++)
{
}
}
int nodo_inicial;
int nodo_final;
int z=1;
mm:
scanf("%d",&nodo_inicial
);
nodo_inicial=nodo_inicial-1;
nodo_final=nodo_final-1;
if (nodo_inicial<nodo_final){
Dijkstra(matriz,nodo_inicial,nodo_final);
if (nodo_inicial>nodo_final){
Dijkstra(matriz,nodo_final,nodo_inicial);
}
goto mm;
return 0;
}
Tu fallo está en que dado un camino te quedas con el tramo más corto, para todo el camino debes devolver la suma de todos los tramos.