El problema del camino más corto: algoritmos y aplicaciones
Por favor, use este identificador para citas ou ligazóns a este ítem:
http://hdl.handle.net/10347/28914
Ficheiros no ítem
Metadatos do ítem
Título: | El problema del camino más corto: algoritmos y aplicaciones |
Autor/a: | Gude Santos, Alba |
Dirección/Titoría: | González-Díaz, Julio |
Centro/Departamento: | Universidade de Santiago de Compostela. Facultade de Matemáticas |
Data: | 2021-07 |
Resumo: | [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. |
Descrición: | Traballo Fin de Grao en Matemáticas. Curso 2020-2021 |
URI: | http://hdl.handle.net/10347/28914 |
Dereitos: | Atribución-NoComercial-CompartirIgual 4.0 Internacional |
Coleccións
-
- Grao en Matemáticas [306]
O ítem ten asociados os seguintes ficheiros de licenza: