El problema del camino más corto: algoritmos y aplicaciones

Abstract

[ES] En esta memoria introduciremos el problema del camino más corto y definiremos distintos tipos de algoritmos para resolverlo. En particular, trataremos de resolver el problema del camino más corto desde un nodo origen a otro nodo de la red. En este trabajo, diferenciaremos los algoritmos en dos capítulos. Primero veremos los algoritmos que resuelven el problema del camino más corto cuando las longitudes de los arcos son no negativas. Después veremos algoritmos más generales, para redes con longitudes arbitrarias que, o bien encuentran el camino más corto, o bien detectan la presencia de ciclos de longitud total negativa. Finalmente, presentaremos algunas aplicaciones prácticas del problema del camino más corto que aparecen en la vida real.

[EN] In this report we will introduce the shortest path problem and define different types of algorithms to solve it. In particular, we will try to solve the shortest path problem from a source node to another node in the network. In this paper, we will differentiate the algorithms in two chapters. First we will look at algorithms that solve the shortest path problem when arc lengths are non-negative. Then we will look at more general algorithms, for networks with arbitrary lengths that either find the shortest path or detect the presence of cycles of negative total length. Finally, we will present some practical applications of the shortest path problem that appear in real life.