Librería sobre grafos en Haskell : el problema del camino más corto

Abstract

The shortest path problem is an important problem in graph theory, consisting in finding paths between two nodes in weighted graphs such that the sum of the weights of their edges is minimized. In addition to its theoretical interest, this problem has applications in various fields, such as social networks, data analysis and route optimization. In this project, we firstly make a theoretical study of the shortest path problem, presenting several algorithms. Then, we discuss the creation of a Haskell library for graphs, focusing on solving the shortest path problem and implementing the previously studied algorithms. Finally, we use the library to find the shortest paths in specific examples.

El problema del camino más corto es un problema de suma importancia en teoría de grafos, que consiste en encontrar caminos entre dos nodos en grafos ponderados tales que la suma de los pesos de sus aristas sea mínima. Además de su interés teórico, este problema tiene aplicaciones en distintos campos, como redes sociales, análisis de datos y optimización de rutas. En este trabajo, en primer lugar haremos un estudio teórico del problema del camino más corto, presentando algunos algoritmos. Después, comentaremos la creación de una librería Haskell sobre grafos, centrándonos en la resolución del problema del camino más corto e implementando los algoritmos previamente estudiados. Finalmente, usaremos la librería para encontrar caminos más cortos en ejemplos concretos.