Código
#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <conio.h> #include <string.h> #define MaxNodos 47 typedef struct nodo_ { int etiqueta; float peso; struct nodo_ *sig; }Tnodo; /** variables globales */ Tnodo *Lista[MaxNodos]; //lista de adyacencia int marca[MaxNodos]; //visitados int predecesores[MaxNodos]; //ruta float d[MaxNodos]; // distancia - peso int Num_Vertices; //numero de vertices int tipo; //1 no dirigido, 0 dirigido char uanl[250][250]; //Arreglo de nombres UANL /** ------------------ */ /* Inicializa la lista de adyacencia a NULL */ void init() { int i; for (i = 0; i < MaxNodos; i++) Lista[i] = NULL; } int lista (int tipo)/*FUNCION QUE DESPLIEGA LA LISTA PARA SELECCIONAR LA OPCION DEL USUARIO*/ { int val=0; do { int j=0; switch(tipo) { for(j=1;j<=28;j++) break; for(j=29;j<=47;j++) break; }; }while(val<1 || val > 47); return val; } /* Inserta los vertices en la lista de adyacencia */ void inserta (int Vorigen, int Vfinal, float peso) { Tnodo *q; if (!q) return; //hubo un error q->etiqueta = Vfinal-1; q->peso = peso; q->sig = NULL; if (Lista[Vorigen-1] != NULL) q->sig = Lista[Vorigen-1]; Lista[Vorigen-1] = q; } /* Libera la lista de adyacencia */ void liberar_lista (void) { Tnodo *q; int i; for (i = 0; i < Num_Vertices; i++) { if (Lista[i] != NULL) { while (Lista[i] != NULL) { q = Lista[i]; Lista[i] = Lista[i]->sig; } } //--fin si (no necesarias las llaves) } //--fin for (no necesaria las llaves) } /* Carga el grafo desde un fichero */ void cargar_grafo (char *fn) { FILE *fp; int v_in, v_fn; //vertice inicial y final float peso; getche(); } inserta(v_in, v_fn, peso); inserta (v_fn, v_in, peso); } } // fin cargar_grafo void cargar_nombres (char *fn) { FILE *fp; getche(); } int i=1; char caracteres[150]; { i++; } } // fin cargar_nombres /* Retorna el peso de la arista que une dos nodos */ float return_peso (int origen, int destino) { Tnodo *p; int encontrado; encontrado = 0; p = Lista[origen]; while (p != NULL && !encontrado) { if (p->etiqueta == destino) encontrado = 1; else p = p->sig; } return p->peso; } int menor_valor() { int i, verticeMenor; float menor; menor = INT_MAX; for (i = 0; i < Num_Vertices; i++) { if (marca[i] == 0 ) if (menor > d[i]) { menor = d[i]; verticeMenor = i; } } // fin for return verticeMenor; } /* Dijkstra */ void dijkstra (int origen, int destino) { int i, last, x; Tnodo *p; // inicializacion for (i = 0; i < MaxNodos; i++) { d[i] = INT_MAX; //"infinito" marca[i] = 0; predecesores[i] = -1; } // -- d[origen] = 0; marca[origen] = 1; last = origen; while (marca[destino] == 0) { //hasta que no lleguemos al destino p = Lista[last]; while (p != NULL){ //para todos los nodos adyacendes if (marca[p->etiqueta] == 0) //si no ha sido visitado if (d[p->etiqueta] > d[last] + return_peso(last, p->etiqueta)) { d[p->etiqueta] = d[last] + return_peso(last, p->etiqueta); predecesores[p->etiqueta] = last; } // fin si p = p->sig; } // fin mientras x = menor_valor(); marca[x] = 1; last = x; } // fin mientras } /* Imprime la ruta por pantalla */ void ImprimirCamino(int v) { if (v != -1) ImprimirCamino(predecesores[v]); if (v != -1) //evitamos que se imprima el -1 { } } /* Menu de opciones */ int menu() { int opcion; do { }while (opcion < 0 || opcion > 1); return opcion; } /* Funcion principal */ int main () { char file[25]; int origen, destino,opi,tipo=0; int salir = 0; getche(); init(); do { switch(menu()) { case 0: salir = 1; break; case 1: while(tipo!=1&&tipo!=2) { printf("\n\tSi desea partir de una facultad introduzca 1\n\tSi desea partir de una preparatoria introduca 2....._"); } origen = lista (tipo); tipo=0; while(tipo!=1&&tipo!=2) { printf("\n\tSi desea llegar de una facultad introduzca 1\n\tSi desea llegar de una preparatoria introduca 2....._"); } destino= lista (tipo); dijkstra(origen-1, destino-1); ImprimirCamino(destino-1); break; }; //final switch tipo=0; }while(!salir); liberar_lista(); }
MOD: Etiqueta GeSHi.