Algoritmo de Dijkstra, publicado por Edsger Dijkstra en 1959, es un poderoso método para encontrar caminos más cortos entre vértices de un grafo. Este Instructable contiene los pasos de este algoritmo, para ayudarle con siguiendo el algoritmo sobre el papel o implementar en un programa.
Tenga en cuenta que los pasos indicados sólo registran las longitudes de camino más cortas y no guarde los caminos reales más cortos a lo largo de los vértices. Si se desea el conocimiento de la composición de los caminos, pasos 2 y 4 pueden modificarse fácilmente para guardar estos datos en otro array asociativo: ver artículo de 1959 de Dijkstra en Numerische Mathematik para obtener más información.
Bien, vamos a empezar! En estas instrucciones, suponemos que tenemos la siguiente información:
- Un gráfico G
- Un conjunto de vértices V
- Un conjunto de bordes E (donde cada arista tiene un peso negativo)
- Punto de partida s ∈ V
Tenga en cuenta que el "elemento", ∈, indica que el elemento en el lado izquierdo del símbolo está contenido dentro de la colección al otro lado del símbolo. Por ejemplo, s ∈ V indica que s es un elemento de V , en este caso, esto significa que s es un vértice dentro de la gráfica.
Estas instrucciones están diseñadas para su uso por un público familiarizado con los fundamentos de la teoría de grafos, teoría de conjuntos y estructuras de datos. Con este requisito previo conocimiento, notación y los conceptos utilizados deben ser relativamente simples para el público.
Para obtener más información sobre los detalles del algoritmo de Dijkstra, la Página de Wikipedia de es un recurso excelente.
