Resumen

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.

• Materias:Modelos matemáticos Investigación operacional Administración de empresas Administración
• Subjects:Mathematical models Operations research Business enterprises Management
• Palabras claves:Ciencias de la administración, Teoría de grafos, Modelos de redes, Algoritmo de Dijkstra, digrafo, Digrafo ponderado, Digrafo pesado, Peso de un camino, Camino de coste mínimo, Camino mínimo
• Keywords:Administration sciences, Graph theory, Network models, Dijkstra algorithm, digraph, Weighted digraph, Heavy digraph, Weight of a road, Minimum cost path, Minimum path