Modelos de redes
Investigación de operaciones. Segunda entrega
Esta sección es una extensión de la anterior. Se muestran técnicas y problemas más específicos, incluyendo algunos algoritmos específicos (Dijkstra, Kronecker), camino crítico, camino más corto, flujo máximo, árbol de recubrimiento mínimo.
- Video:Teoría de grafos en la vida real. Grafos ponderados. Algoritmo de Dijkstra. ©UPV
- Fuente:Canal Universitat Politècnica de València UPV / YouTube
Acerca del algoritmo de Dijkstra
On the Dijkstra algorithm
El algoritmo de Dijkstra es de tipo voraz (algoritmo goloso) que genera uno a uno los caminos de un nodo a al resto por orden creciente de longitud. Usa un conjunto S de vértices donde, a cada paso del algoritmo, se guardan los nodos para los que ya se sabe el camino mínimo y devuelve un vector indexado por vértices, de modo que para cada uno de estos se puede determinar el coste de un camino más económico (de peso mínimo) de a a tales vértices. En este documento se realiza una descripción detallada del algoritmo de Dijkstra, justificando su correctitud, discutiendo y mostrando algunas de sus aplicaciones.
Este escrito fue elaborado por Álvaro H. Salas S. (Departamento de Matemáticas, Universidad Nacional de Colombia sede Manizales, Manizales, Colombia). Se encuentra alojado en la página de arXiv.org, depósito institucional fundado y mantenido por la Cornell University Library (Cornell University. Ithaca, NY, Estados Unidos).
