| TAZ-TFG-2018-2466 |
Problema de todos los pares de caminos óptimos en un grafo
Sánchez Fabián, Lorenzo
García Olaverri, Alfredo (dir.)
Universidad de Zaragoza,
CIEN,
2018
Departamento de Métodos Estadísticos, Área de Estadística e Investigación Operativa
Graduado en Matemáticas
Resumen: El trabajo consiste en el estudio del problema de todos los pares de caminos óptimos en un grafo. Para proceder a ello explicamos los conceptos de grafo y complejidad computacional y damos el algoritmo de Floyd-Warshall para resolverlo, haciendo también un análisis de su complejidad. También vemos que este problema es equivalente a un problema matricial. Finalmente explicamos un algoritmo más reciente ideado por Timothy M. Chan que resuelve este problema pero con un coste computacional menor en un factor logarítmico.
Tipo de Trabajo Académico: Trabajo Fin de Grado
Notas: Vuelvo a subir el documento porque me he dado cuenta de que en el que he subido anteriormente había un par de erratas.
Enlace permanente:
El registro pertenece a las siguientes colecciones:
Trabajos académicos > Trabajos Académicos por Centro > Facultad de Ciencias
Trabajos académicos > Trabajos fin de grado