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
Código
#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); 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]; } } 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: 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; }