[Grafo] Base para el Algoritmo de Dijkstra

[AlbertoBSD]

Muy buen dia, les dejo la Base para realizar el algoritmo de dijkstra.

La imagen de ejemplo es la que esta en Wikipedia https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#/media/File:Dijkstra_Animation.gif

He aqui el código, el ejemplo que muestra que la ruta mas rápida de 1 a 5 tiene un peso total de 20

El código esta medianamente comentado y Imprime lo que esta haciendo en tiempo de ejecución.

Código (c) [Seleccionar] Expandir

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct nodo {
int id;
//Dato del Nodo
//struct data *datos; //En caso de apuntar a otro tipo de estrucutura
//Variables auxiliar para el Grafo
int peso_actual; //Contenedor del peso actual recorrido para llegar a este nodo
struct nodo *mejor_ruta; //Indice de la mejor ruta para llegar al nodo de la ultima busqueda -1 para datos no inicializados
int visitado; //Variable Entera de Visitado, almacena un numero Ramdon para deteminar si fue visitado o no por el proceso actual
int out;
int total; //Total de vetices conectados a reste Nodo
int *aristas; //En caso de que existan distintos pesos para viajar al X vertice se ponen aqui
struct nodo **vertices; //Distintos vertices que se pueden alcanzar desde este Nodo
//int *vertices; //En caso de aplicar un nodo por indices a un arreglo de nodos
};

struct grafo {
int total; // Total de nodos validos en el grafo
int disponible; // Total de espacios asignables en el grafo
struct nodo **nodos; //tabla de acceso rapido a X nodo
};


struct grafo *add(struct grafo *grafo_actual,int origen, int peso, int destino);
void add_nodo(struct grafo *grafo_actual,int origen,int peso,int destino);
int dijkstra(struct nodo *nodo_a,struct nodo *nodo_b);
int menor_ruta(struct grafo *grafo_actual,int A,int B);

int main() {
struct grafo *grafo = NULL;
/*
struct grafo *add(struct grafo *grafo_actual,int origen, int peso, int destino);
*/
grafo = add(grafo,1, 7,2);
grafo = add(grafo,1, 9,3);
grafo = add(grafo,1,14,6);
grafo = add(grafo,6, 9,5);
grafo = add(grafo,6, 2,3);
grafo = add(grafo,3,11,4);
grafo = add(grafo,3,10,2);
grafo = add(grafo,2,15,4);
grafo = add(grafo,4, 6,5);
printf("Ruta %i\n",menor_ruta(grafo,1,5));
return 0;
}

int menor_ruta(struct grafo *grafo_actual,int A,int B) {
return dijkstra(grafo_actual->nodos[A-1],grafo_actual->nodos[B-1]);
}

struct grafo *add(struct grafo *grafo_actual,int origen, int peso, int destino) {
/*
Variables
*/
int mayor = destino;
struct nodo **temp = NULL;
/*
Inicializamos el grafo en caso de que no exista
*/
if(grafo_actual == NULL) {
grafo_actual = calloc(1,sizeof(struct grafo));
}
/*
Determinamos el indice mayor
*/
if(origen > destino) {
mayor = origen;
}
/*
Evaluamos si tenemos espacio suficiente
*/
if(mayor > grafo_actual->disponible) {
/*
En caso de no tener espacio suficiente lo reasignamos
*/
temp = calloc(mayor,sizeof(struct nodo*));
if(temp) {
if(grafo_actual->nodos) {
memcpy(temp,grafo_actual->nodos,grafo_actual->disponible*sizeof(struct nodo*));
free(grafo_actual->nodos);
grafo_actual->nodos = NULL;
}
grafo_actual->nodos = temp;
grafo_actual->disponible = mayor;
}else {
printf("Memory out!!\n");
exit(0);
}
}
/*
Inicializamos los nodos en caso de que no existan
*/
if(grafo_actual->nodos[origen-1] == NULL) {
grafo_actual->nodos[origen-1] = calloc(1,sizeof(struct nodo));
grafo_actual->nodos[origen-1]->id = origen;
grafo_actual->total++;
}
if(grafo_actual->nodos[destino-1] == NULL) {
grafo_actual->nodos[destino-1] = calloc(1,sizeof(struct nodo));
grafo_actual->nodos[destino-1]->id = destino;
grafo_actual->total++;
}

/*
Agregamos las Pesos y Aristas
*/
add_nodo(grafo_actual,origen,peso,destino);
add_nodo(grafo_actual,destino,peso,origen);

/*
Retornamos el grafo_actual
*/
return grafo_actual;
}

void add_nodo(struct grafo *grafo_actual,int origen,int peso,int destino) {
struct nodo *aux = grafo_actual->nodos[origen-1];
aux->aristas = realloc(aux->aristas,sizeof(int)*(aux->total+1));
aux->vertices = realloc(aux->vertices,sizeof(int)*(aux->total+1));
aux->aristas[aux->total]  = peso;
aux->vertices[aux->total] = grafo_actual->nodos[destino-1];
printf("Uniendo nodos: (%i)--[%i]--(%i)\n",origen,peso,destino);
aux->total++;
}

int dijkstra(struct nodo *nodo_a,struct nodo *nodo_b) {
struct nodo *inicio =NULL,*pivote = NULL;
struct nodo **pendientes = NULL; //Arreglo de nodos no visitados a un.
int i,j,total = 0;
int visitado = rand(); //Variable aleatoria para determinar si un Nodo ya fue visitado por esta ocacion
int peso_nuevo; //Variable temporal para evaluar cual es el menor peso al momento de visitar un nodo
i = 0;
pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
pendientes[total] = nodo_a; //Nodo inicial a visitar el el nodo A que se recibio como parametr
nodo_a->peso_actual = 0;
total++;
printf("Buscando ruta de %i a %i\n",nodo_a->id,nodo_b->id);
while(i < total) {
pivote = pendientes[i];
printf("Procesando el nodo %i\n",pivote->id);
if(pivote->out != visitado){ //Si aun no Agotamos el nodo actual
printf("Visitando %i\n",pivote->id);
j = 0;
while(j < pivote->total ) {
if(pivote->vertices[j]->out != visitado) {
if(pivote->vertices[j]->visitado != visitado) {
printf("El subnodo %i no a sido visitado\n",pivote->vertices[j]->id);
pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
pendientes[total] = pivote->vertices[j];
total++;
pivote->vertices[j]->peso_actual = pivote->peso_actual + pivote->aristas[j];
pivote->vertices[j]->mejor_ruta = pivote;
//printf("Ruta de %i a %i vale %i\n",nodo_a->id,pivote->vertices[j]->id,pivote->vertices[j]->peso_actual);
}
else { //Aqui ya lo visitamos, solo validaremos si la ruta pesa menos por este camino que por que se visito previamente
printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
//printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
peso_nuevo =  pivote->peso_actual + pivote->aristas[j];
printf("%i > %i ? %s\n",pivote->vertices[j]->peso_actual,peso_nuevo,(pivote->vertices[j]->peso_actual > peso_nuevo) ? "si":"no");
if(pivote->vertices[j]->peso_actual > peso_nuevo) { // Si esta condicion se cumple es mas rapido llegar al nodo pivote->vertices[j] mediante el nodo pivote
printf("Nueva mejor ruta a %i con peso de %i\n",pivote->vertices[j]->id,peso_nuevo);
pivote->vertices[j]->peso_actual = peso_nuevo;
pivote->vertices[j]->mejor_ruta = pivote;
}
printf("Ruta de %i a %i vale %i\n",nodo_a->id,pivote->vertices[j]->id,pivote->vertices[j]->peso_actual);
//En caso de que el if no se cumpla es mas rapido llegar al nodo pivote->vertices[j] de la manera en la ya habia sido visitado previamente
}
}
else {
//printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
peso_nuevo =  pivote->peso_actual + pivote->aristas[j];
printf("%i > %i ? %s\n",pivote->vertices[j]->peso_actual,peso_nuevo,(pivote->vertices[j]->peso_actual > peso_nuevo) ? "si":"no");
if(pivote->vertices[j]->peso_actual > peso_nuevo) { // Si esta condicion se cumple es mas rapido llegar al nodo pivote->vertices[j] mediante el nodo pivote
printf("Nueva mejor ruta a %i con peso de %i\n",pivote->vertices[j]->id,peso_nuevo);
pivote->vertices[j]->peso_actual
= peso_nuevo;
pivote->vertices[j]->mejor_ruta = pivote;
}
printf("Ruta de %i a %i vale %i\n",nodo_a->id,pivote->vertices[j]->id,pivote->vertices[j]->peso_actual);
//En caso de que el if no se cumpla es mas rapido llegar al nodo pivote->vertices[j] de la manera en la ya habia sido visitado previamente
}
pivote->vertices[j]->visitado = visitado;
j++;
}
pivote->out = visitado;
printf("Nodo %i fuera!\n",pivote->id);
}
else {
printf("El nodo %i ya esta fuera\n",pivote->id);
}
i++;
}
free(pendientes);
return nodo_b->peso_actual;
}


[class_OpenGL]

Esto me vendrá bien para aprender el tema de los grafos. ¡Gracias!