Mensajes

Hola querida comunidad

Necesito hacer un proyecto de una aplicación de medios de transporte

Ya tengo todo salvo en el algoritmo que utilizare

Debo utilizar el Algoritmo de Dijkstra en lenguaje C o C++ para encontrar las rutas más cortas, sin embargo el que tengo me genera errores y en verdad me urge

Me genera rutas pero en ocasiones no son las más cortas, sigo trabajando en ello pero neta me urge tener correcto el algoritmo

Si alguien tiene un código del algoritmo de Dijkstra, me lo podrían proporcionar???
De antemano muchas gracias y excelente día

[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]

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

Código (c) [Seleccionar] Expandir


#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++)
{

printf ("%d ", visita[j]+1);
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++)
{
printf(" %d", matriz[i][j]);
}
printf("\n");
}
printf("\n\n\n");
int nodo_inicial;
int nodo_final;
int z=1;
mm:
printf("Nodo inicial--> ");
scanf("%d",&nodo_inicial);
printf("Nodo final--> ");
scanf("%d",&nodo_final);
printf("\n\n");

nodo_inicial=nodo_inicial-1;
nodo_final=nodo_final-1;

if (nodo_inicial<nodo_final){
Dijkstra(matriz,nodo_inicial,nodo_final);
printf("\n\n");  }

if (nodo_inicial>nodo_final){
Dijkstra(matriz,nodo_final,nodo_inicial);
printf("\n\n");
}
goto mm;

return 0;
}


Hola comunidad!!!

Publico esto para pedir su ayuda

Necesito realizar un programa que me de las diferentes rutas posibles dentro de un grafo

Entiendo que esto lo puedo realizar con una matriz de Adyacencia con 1 y 0

Como podría realizar este procedimiento???
     L
    /
C ---B----D
|\            |
| \           |
A---F------H     

Por ejemplo en este grafo me las rutas para ir de A a L
A->C->L   ,    A->F->C->L    ,    A->F->H->D->B->C->L

Hola amigos!
Es la primera vez que escribo aqui y espero me puedan brindar un poco de su ayuda
Tengo que realizar un programa usando estructuras de arboles y de listas pero tengo un problema con estas ultimas

Quiero añadir un nuevo nodo a mi lista y la llamada de la funcion me quedaria asi
---->    Lista=Alta(Lista,"dato int", "dato char");

Lo que quiero es que de un arreglo yo extraiga uno de sus elementos y lo ponga en mi funcion como parametro de este modo --->  Lista=Alta(Lista,conta_frec, diccionario[0]);

Sin embargo me genera error

Como puedo darle el parametro a mi funcion de un solo elementos de mi arreglo????


Ayuda!!!! :'c