RT Generic
T1 El problema del camino más corto: algoritmos y aplicaciones
A1 Gude Santos, Alba
AB [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 problemadel 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 resuelvenel 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, obien encuentran el camino más corto, o bien detectan la presencia de ciclos de longitudtotal negativa. Finalmente, presentaremos algunas aplicaciones prácticas del problema delcamino más corto que aparecen en la vida real.
AB [EN] In this report we will introduce the shortest path problem and define different typesof algorithms to solve it. In particular, we will try to solve the shortest path problemfrom a source node to another node in the network. In this paper, we will differentiate thealgorithms in two chapters. First we will look at algorithms that solve the shortest pathproblem 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 presenceof cycles of negative total length. Finally, we will present some practical applications ofthe shortest path problem that appear in real life.
YR 2021
FD 2021-07
LK http://hdl.handle.net/10347/28914
UL http://hdl.handle.net/10347/28914
LA spa
NO Traballo Fin de Grao en Matemáticas. Curso 2020-2021
DS Minerva
RD 24 abr 2026