Análisis e implementación de un algoritmo incrustado en un administrador de base de datos relacional, para encontrar la ruta más corta entre dos puntos geográficos.

Abstract

El trabajo consiste en el estudio comparativo de tres algoritmos que permiten obtener la ruta más corta (Dijkstra, Bellman-Ford y Floyd-Warshall) contra el algoritmo implementado en el megaproyecto de Averiguate. Estos algoritmos fueron traducidos a lenguaje SQL para poder implementarlos en una base de datos relacional, por medio de procedimientos almacenados. Para el experimento se creó una base de datos que permitiera almacenar la información de las direcciones de la zona 10 y una aplicación web para poder realizar las pruebas con los algoritmos a comparar. Se realizó una encuesta a miembros de la Universidad del Valle de Guatemala y el algoritmo favorecido fue el de Dijkstra. Adicionalmente se llevaron a cabo pruebas técnicas que evaluaron el rendimiento de los cuatro algoritmos involucrados. Estas pruebas consisten en generar rutas entre todas las direcciones que se guardaron en la base de datos para determinar el promedio que cada algoritmo se tarda en generar cada ruta y el total de tiempo que se tarda en generar todas las rutas. Se determinó que el algoritmo de Dijkstra permite a los usuarios encontrar el camino más corto entre dos direcciones en un menor tiempo. RR