Nuevos algoritmos para la resolución del problema del camino mínimo basados en el método radix y en el preestudio de la red

Abstract

ESTE TRABAJO DE INVESTIGACION SE HA DESARROLLADO PARA RESOLVER UN PROBLEMA CONCRETO: HALLAR EL CAMINO MINIMO ENTRE DOS NODOS EN UNA RED NO ORIENTADA, EL ESTUDIO SE CENTRO EN TRES ASPECTOS DIFERENTES. EL PRIMERO ES ANALIZAR LAS FORMAS DE ALMACENAMIENTO DE REDES. EN ESTA TESIS SE HA DESARROLLADO UN NUEVO METODO BASADO EN LA LISTA DE ADYACENCIA, QUE OCUPA UN VECTOR DE TAMAÑO M, NUMERO DE ARCOS DE LA RED, MENOS QUE EL METODO ORIGINAL, ADECUADO PARA REDES NO ORIENTADAS. EL SEGUNDO ASPECTO SE REFIERE A LA MEJORA DE LOS ALGORITMOS DERIVADOS DEL METODO RADIX, Y LA INTRODUCCION DE UN NUEVO ALGORITMO, LLAMADO DE SEGMENTOS VARIABLES, BASADO EN EL METODO RADIX DE DOS NIVELES. POR ULTIMO, SE HA DESARROLLADO UN NUEVO ALGORITMO ADECUADO PARA RESOLVER EL PROBLEMA DEL CAMINO MINIMO ENTRE DOS NODOS EN UNA RED NO ORIENTADA, LLAMADO METODO DE LAS COORDENADAS. SE BASA EN EL ESTUDIO PREVIO DE LA RED, DE FORMA QUE A CADA NODO SE LE ASIGNA UNA O VARIAS COORDENADAS. EL RESULTADO ES COMO SI EL ALGORITMO BUSCARA EL NODO DESTINO, DESCARTANDO LOS NODOS QUE NO ESTEN EN SU DIRECCION. ESTO HACE QUE SE REDUZCAN SIGNIFICATIVAMENTE LOS TIEMPOS DE EJECUCION.