El algoritmo de Dijkstra

El algoritmo de Dijkstra ( / ˈ d aɪ k . s t r ə z / , DYKE -strəz ) es un algoritmo para encontrar los caminos más cortos entre nodos en un grafo ponderado , que puede representar, por ejemplo, una red de carreteras . Fue concebido por el científico informático Edsger W. Dijkstra en 1956 y publicado tres años después. ^{[ 4 ] [ 5 ] [ 6 ]}

El algoritmo de Dijkstra encuentra la ruta más corta desde un nodo de origen dado a todos los demás nodos. ^{[ 7 ] : 196–206} Puede utilizarse para encontrar la ruta más corta a un nodo de destino específico, terminando el algoritmo después de determinar la ruta más corta a ese nodo. Por ejemplo, si los nodos del grafo representan ciudades y los costos de las aristas representan las distancias entre pares de ciudades conectadas por una carretera directa, entonces el algoritmo de Dijkstra puede utilizarse para encontrar la ruta más corta entre una ciudad y todas las demás ciudades. Una aplicación común de los algoritmos de ruta más corta son los protocolos de enrutamiento de red , en particular IS-IS (Intermediate System to Intermediate System) y OSPF (Open Shortest Path First). También se emplea como subrutina en algoritmos como el algoritmo de Johnson .

El algoritmo utiliza una estructura de datos de cola de prioridad mínima para seleccionar las rutas más cortas conocidas hasta ahora. Antes de que se descubrieran estructuras de cola de prioridad más avanzadas, el algoritmo original de Dijkstra se ejecutaba en${\displaystyle \Theta (|V|^{2})}$tiempo , donde${\displaystyle |V|}$es el número de nodos. ^{[ 8 ] [ 9 ]} Fredman y Tarjan 1984 propusieron una cola de prioridad de montón de Fibonacci para optimizar la complejidad del tiempo de ejecución a${\displaystyle \Theta (|E|+|V|\log |V|)}$, dónde${\displaystyle |E|}$es el número de aristas. Este es asintóticamente el algoritmo de ruta más corta de origen único más rápido conocido para grafos dirigidos arbitrarios con pesos no negativos no acotados. Sin embargo, los casos especializados (como pesos acotados/enteros, grafos dirigidos acíclicos, etc.) pueden mejorarse aún más . Si se permite el preprocesamiento, algoritmos como las jerarquías de contracción pueden ser hasta siete órdenes de magnitud más rápidos.

El algoritmo de Dijkstra se usa comúnmente en grafos donde los pesos de las aristas son enteros positivos o números reales. Se puede generalizar a cualquier grafo donde los pesos de las aristas estén parcialmente ordenados , siempre que las etiquetas subsiguientes (se produce una etiqueta subsiguiente al recorrer una arista) sean monótonamente no decrecientes. ^{[ 10 ] [ 11 ]}

En muchos campos, particularmente en inteligencia artificial , el algoritmo de Dijkstra o una variante ofrece una búsqueda de costo uniforme y se formula como una instancia de la idea más general de búsqueda primero en amplitud . ^{[ 12 ]}

¿Cuál es la ruta más corta para viajar de Rotterdam a Groningen , en general: de una ciudad a otra? Se trata del algoritmo para la ruta más corta , que diseñé en unos veinte minutos. Una mañana, estaba de compras en Ámsterdam con mi joven prometida, y cansados, nos sentamos en la terraza de un café a tomar una taza. Estaba pensando si podría hacer esto, y entonces diseñé el algoritmo para la ruta más corta. Como dije, fue un invento de veinte minutos. De hecho, se publicó en 1959, tres años después. La publicación aún se puede leer, de hecho es bastante buena. Una de las razones por las que es tan buena es que la diseñé sin lápiz ni papel. Más tarde aprendí que una de las ventajas de diseñar sin lápiz ni papel es que prácticamente te ves obligado a evitar todas las complejidades evitables. Finalmente, ese algoritmo se convirtió, para mi gran asombro, en una de las piedras angulares de mi fama.

Dijkstra pensó en el problema del camino más corto mientras trabajaba como programador en el Centro Matemático de Ámsterdam en 1956. Quería demostrar las capacidades de la nueva computadora ARMAC. ^{[ 13 ]} Su objetivo era elegir un problema y una solución informática que personas sin conocimientos de informática pudieran entender. Diseñó el algoritmo del camino más corto y posteriormente lo implementó para ARMAC en un mapa de transporte ligeramente simplificado de 64 ciudades de los Países Bajos (lo limitó a 64, de modo que 6 bits serían suficientes para codificar el número de ciudad). ^{[ 5 ]} Un año después, se encontró con otro problema planteado por ingenieros de hardware que trabajaban en la siguiente computadora del instituto: minimizar la cantidad de cable necesaria para conectar los pines del panel posterior de la máquina. Como solución, redescubrió el algoritmo del árbol de expansión mínima de Prim (conocido anteriormente por Jarník y también redescubierto por Prim ). ^{[ 14 ] [ 15 ]} Dijkstra publicó el algoritmo en 1959, dos años después de Prim y 29 años después de Jarník. ^{[ 16 ] [ 17 ]}

El algoritmo requiere un nodo inicial y calcula la distancia más corta desde ese nodo inicial a cada uno de los demás nodos. El algoritmo de Dijkstra comienza con distancias infinitas e intenta mejorarlas paso a paso:

1. Crea un conjunto de todos los nodos no visitados: el conjunto de nodos no visitados.
2. Asigne a cada nodo un valor de distancia desde el inicio: para el nodo inicial, es cero, y para todos los demás nodos, es infinito, ya que inicialmente no se conoce ningún camino hacia estos nodos. Durante la ejecución, la distancia de un nodo N es la longitud del camino más corto descubierto hasta el momento entre el nodo inicial ^y N. ^{[ 18} ]
3. Del conjunto de nodos no visitados, seleccione el nodo actual con la distancia más pequeña (finita); inicialmente, este es el nodo de partida (distancia cero). Si el conjunto de nodos no visitados está vacío o contiene solo nodos con distancia infinita (que son inaccesibles), el algoritmo finaliza pasando al paso 6. Si el único objetivo es la ruta hacia un nodo de destino, el algoritmo finaliza cuando el nodo actual es el nodo de destino. De lo contrario, el algoritmo continúa.
4. Para el nodo actual, considere todos sus vecinos no visitados y actualice sus distancias a través del nodo actual; compare la distancia recién calculada con la que actualmente tiene asignada y asígnele la menor. Por ejemplo, si el nodo actual A tiene una distancia de 6 y la arista que lo conecta con su vecino B tiene una longitud de 2, entonces la distancia a B a través de A es 6 + 2 = 8. Si B tenía previamente una distancia mayor que 8, actualícela a 8 (el camino a B a través de A es más corto). De lo contrario, mantenga su distancia actual (el camino a B a través de A no es el más corto).
5. Tras considerar todos los vecinos no visitados del nodo actual, este se elimina del conjunto de no visitados. Por lo tanto, un nodo visitado nunca se vuelve a comprobar, lo cual es correcto, ya que la distancia registrada en el nodo actual es mínima (como se verificó en el paso 3) y, por consiguiente, definitiva. Repita desde el paso 3.
6. Una vez que finaliza el bucle (pasos 3 a 5), ​​cada nodo visitado contiene la distancia más corta desde el nodo de inicio.

Este algoritmo permite encontrar la ruta más corta entre dos intersecciones en un mapa de la ciudad utilizando lápiz y papel. Cada intersección se muestra en una línea separada: una es el punto de partida y se etiqueta con una distancia de 0. Las demás intersecciones se etiquetan inicialmente con una distancia de infinito. Esto indica que aún no se ha establecido ninguna ruta hacia estas intersecciones. En cada iteración, una intersección se convierte en la intersección actual. En la primera iteración, esta es el punto de partida.

Desde la intersección actual, se calcula la distancia a cada intersección vecina (conectada directamente) sumando la etiqueta (valor) de la intersección actual y la distancia a la vecina, y luego reetiquetando a la vecina con el menor valor entre esa suma y la etiqueta existente de la vecina. Es decir, se reetiqueta a la vecina si el camino hacia ella a través de la intersección actual es más corto que los caminos evaluados previamente. En ese caso, se marca el camino hacia la vecina con una flecha que la señala y se borra cualquier otra flecha que apunte hacia ella. Una vez evaluadas las distancias a cada una de las vecinas de la intersección actual, esta se marca como visitada. La intersección no visitada con la etiqueta más pequeña se convierte en la intersección actual y el proceso se repite hasta que se hayan visitado todos los nodos con etiquetas menores que la etiqueta de destino.

Una vez que no queden nodos sin visitar con una etiqueta menor que la etiqueta del destino, las flechas restantes mostrarán la ruta más corta.

En el siguiente pseudocódigo , `dist` es un array que contiene las distancias actuales desde el origen a otros vértices, es decir, `dist[ u ]` es la distancia actual desde el origen al vértice `u` . El array `prev` contiene punteros a los nodos de salto anterior en el camino más corto desde el origen al vértice dado (equivalentemente, es el siguiente salto en el camino desde el vértice dado al origen). El código `u ← vértice en Q con min dist[u] ` busca el vértice `u` en el conjunto de vértices Q que tenga el menor valor de `dist[ u ]` . `Graph.Distance( u , v )` devuelve la longitud de la arista que une (es decir, la distancia entre) los dos nodos vecinos `u` y `v` . La variable `alt` en la línea 14 es la longitud del camino desde el nodo de origen al nodo vecino `v` si pasara por `u` . Si este camino es más corto que el camino más corto registrado actualmente para `v` , entonces la distancia de `v` se actualiza a `alt` . ^{[ 7 ]}

 1 function Dijkstra(Graph, source): 2 3 for each vertex v in Graph.Vertices: 4 dist[v] ← INFINITY 5 prev[v] ← UNDEFINED 6 add v to Q 7 dist[source] ← 0 8 9 whileQ is not empty: 10 u ← vertex in Q with minimum dist[u] 11 Q.remove(u) 12 13 for each edge (u, v) in Graph: 14 alt ← dist[u] + Graph.Distance(u,v) 15 ifalt < dist[v]: 16 dist[v] ← alt 17 prev[v] ← u 18 19 return dist[], prev[]

To find the shortest path between vertices source and target, the search terminates after line 10 if u = target. The shortest path from source to target can be obtained by reverse iteration:

1 S ← empty sequence 2 u ← target 3 if prev[u] is defined oru = source: // Proceed if the vertex is reachable 4 whileu is defined: // Construct shortest path with stack S 5 S.push(u) // Push the vertex onto the stack 6 u ← prev[u] // Traverse from target to source

Now sequence S is the list of vertices constituting one of the shortest paths from source to target, or the empty sequence if no path exists.

Un problema más general consiste en encontrar todos los caminos más cortos entre origen y destino (puede haber varios de la misma longitud). En lugar de almacenar un solo nodo en cada entrada de prev[], se pueden almacenar todos los nodos que satisfacen la condición de relajación. Por ejemplo, si tanto r como origen se conectan con destino y se encuentran en diferentes caminos más cortos a través de destino (porque el coste de la arista es el mismo en ambos casos), entonces tanto r como origen se añaden a prev[ target ] . Cuando el algoritmo finaliza, la estructura de datos prev[] describe un grafo que es un subconjunto del grafo original con algunas aristas eliminadas. Su propiedad clave es que si el algoritmo se ejecutó con algún nodo inicial, entonces cada camino desde ese nodo a cualquier otro nodo en el nuevo grafo es el camino más corto entre esos nodos del grafo, y todos los caminos de esa longitud del grafo original están presentes en el nuevo grafo. Entonces, para encontrar realmente todos estos caminos más cortos entre dos nodos dados, un algoritmo de búsqueda de caminos en el nuevo grafo, como la búsqueda en profundidad, sería adecuado.

1 función Dijkstra( Grafo , fuente ): 2 Q ← Cola que almacena la prioridad del vértice 3 4 dist[ source ] ← 0 // Inicialización 5 Q .add_with_priority( source , 0) // la prioridad asociada es igual a dist[·] 6 7 para cada vértice v en Graph.Vertices : 8 si v ≠ origen 9 prev[ v ] ← INDEFINIDO // Predecesor de v 10 dist[ v ] ← INFINITO // Distancia desconocida desde el origen hasta v 11 Q.add_with_priority(v, INFINITY) 12 13 14 mientras Q no esté vacío: // El bucle principal 15 u ← Q .extract_min() // Eliminar y devolver el mejor vértice 16 para cada arista (u, v) : // Recorrer todos los vecinos v de u 17 alt ← dist[ u ] + Graph.Distance( u , v ) 18 si alt < dist[ v ]: 19 prev[ v ] ← u 20 dist[ v ] ← alt 21 Q .decrease_priority( v , alt ) 22 23 retorno (dist, prev)

Para demostrar la corrección del algoritmo de Dijkstra, se puede utilizar la inducción matemática sobre el número de nodos visitados. ^{[ 22 ]}

Hipótesis invariante : Para cada nodo visitado v , es la distancia más corta desde el origen hasta v , y para cada nodo no visitado u , es la distancia más corta desde el origen hasta u viajando solo a través de nodos visitados, o infinito si no existe tal ruta. (Nota: no asumimos que sea la distancia más corta real para nodos no visitados, mientras que es la distancia más corta real).dist[v]dist[u]dist[u]dist[v]

Los límites del tiempo de ejecución del algoritmo de Dijkstra en un grafo con aristas E y vértices V se pueden expresar como una función del número de aristas, denotado${\displaystyle |E|}$y el número de vértices, denotado${\displaystyle |V|}$, utilizando la notación de la gran O. El límite de complejidad depende principalmente de la estructura de datos utilizada para representar el conjunto Q. A continuación, los límites superiores se pueden simplificar porque${\displaystyle |E|}$es${\displaystyle O(|V|^{2})}$para cualquier grafo simple, pero esa simplificación ignora el hecho de que en algunos problemas, existen otros límites superiores en${\displaystyle |E|}$puede retener.

Para cualquier estructura de datos para el conjunto de vértices Q , el tiempo de ejecución es: ^{[ 2 ]}

$${\displaystyle \Theta (|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} }),}$$

dónde${\displaystyle T_{\mathrm {dk} }}$y${\displaystyle T_{\mathrm {em} }}$son las complejidades de las operaciones de disminución de clave y extracción de mínimo en Q , respectivamente.

La versión más simple del algoritmo de Dijkstra almacena el conjunto de vértices Q como una lista enlazada o matriz, y las aristas como una lista de adyacencia o matriz . En este caso, extraer el mínimo es simplemente una búsqueda lineal a través de todos los vértices en Q , por lo que el tiempo de ejecución es${\textstyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}$.

Para grafos dispersos , es decir, grafos con muchos menos que${\displaystyle |V|^{2}}$En cuanto a los bordes, el algoritmo de Dijkstra se puede implementar de manera más eficiente almacenando el grafo en forma de listas de adyacencia y utilizando un árbol de búsqueda binaria autoequilibrado , un montículo binario , un montículo de emparejamiento , un montículo de Fibonacci o un montículo de prioridad como cola de prioridad para implementar la extracción del mínimo de manera eficiente. Para realizar pasos de disminución de clave en un montículo binario de manera eficiente, es necesario utilizar una estructura de datos auxiliar que mapee cada vértice a su posición en el montículo y actualizar esta estructura a medida que cambia la cola de prioridad Q. Con un árbol de búsqueda binaria autoequilibrado o un montículo binario, el algoritmo requiere${\estilo de texto \Theta ((|E|+|V|)\log |V|)}$tiempo en el peor de los casos; para grafos conectados, este límite de tiempo se puede simplificar a${\estilo de texto \Theta (|E|\log |V|)}$. El montón de Fibonacci mejora esto a${\estilo de texto \Theta (|E|+|V|\log |V|)}$.

Cuando se utilizan montículos binarios, la complejidad temporal del caso promedio es menor que la del peor caso: suponiendo que los costos de los bordes se extraen independientemente de una distribución de probabilidad común , el número esperado de operaciones de disminución de clave está acotado por${\displaystyle \Theta (|V|\log(|E|/|V|))}$, lo que da un tiempo total de ejecución de ^{[ 7 ] : 199–200}

$${\displaystyle O\left(|E|+|V|\log {\frac {|E|}{|V|}}\log |V|\right).}$$

El procedimiento uniform_cost_search(start) es nodo ← inicio frontera ← cola de prioridad que contiene solo el nodo expandido ← conjunto vacío Si la frontera está vacía, entonces devolver error . nodo ← frontera.pop() Si el nodo es un estado objetivo, entonces devuelve solution(node). expandido.agregar(nodo) para cada uno de los vecinos del nodo n hacer si n no está en expansión y no está en frontera entonces frontera.agregar( n ) sino si n está en frontera con mayor costo reemplazar el nodo existente con n

Dijkstra bidireccional

El algoritmo de Dijkstra bidireccional es una variante del algoritmo de Dijkstra diseñada para calcular eficientemente el camino más corto entre un vértice de origen s y un vértice de destino t , en lugar de entre todos los vértices. La idea clave es realizar dos búsquedas simultáneas: una hacia adelante desde s en el grafo original y otra hacia atrás desde t en el grafo con las aristas invertidas. Cada búsqueda mantiene sus propias estimaciones de distancia tentativas, una cola de prioridad y un conjunto de vértices "establecidos". Las dos fronteras avanzan una hacia la otra y se encuentran en algún punto del camino más corto entre s y t . ^{[ 27 ]}

Se mantienen dos arreglos de distancia: d _f [ v ] (distancia de s a v ) y d _b [ v ] (distancia de v a t ), inicializados a ∞ excepto d _f [ s ] = 0 y d _b [ t ] = 0 . Dos colas de prioridad Q _f y Q _b contienen vértices que aún no se han procesado completamente, y dos conjuntos S _f y S _b almacenan vértices cuya distancia de camino más corto se ha finalizado en cada dirección. Una variable μ almacena la longitud del mejor camino completo s–t encontrado hasta el momento, inicialmente ∞ .

El algoritmo extrae repetidamente el vértice de distancia mínima de la cola que actualmente tenga la clave más pequeña, relaja sus aristas salientes (o entrantes) y actualiza μ cada vez que descubre una conexión entre los dos conjuntos establecidos:

${\displaystyle \mu \leftarrow \min(\mu ,\;d_{f}[u]+w(u,x)+d_{b}[x])}$al relajar el borde${\displaystyle (u,x)}$en la búsqueda hacia adelante y${\displaystyle x\in S_{b}}$,

y simétricamente para la búsqueda hacia atrás.

Una característica clave es la condición de parada: una vez que la suma de las prioridades mínimas actuales en ambas colas sea al menos μ , ningún camino aún no resuelto puede mejorar μ . En este punto, μ es igual a la verdadera distancia del camino más corto δ( s , t ) , y la búsqueda termina. ^{[ 27 ]}

Este criterio evita el error común de detenerse en cuanto las dos fronteras se tocan, lo que puede pasar por alto una ruta alternativa más corta en otro lugar.

Dado que en los grafos típicos cada búsqueda solo necesita explorar aproximadamente la mitad del espacio de búsqueda, el método bidireccional suele visitar muchos menos vértices y relajar muchas menos aristas que el algoritmo Dijkstra unidireccional en consultas de un solo par. En grafos similares a redes de carreteras, el ahorro puede ser considerable, reduciendo a veces la región explorada de una esfera de tamaño exponencial a dos semiesferas más pequeñas.

El método se utiliza ampliamente en el enrutamiento punto a punto para mapas y software de navegación, y sirve de base para muchas técnicas de aceleración, como ALT, jerarquías de contracción y enrutamiento basado en alcance. ^{[ 28 ]}

Si se desea el camino más corto real (no solo su distancia), se pueden almacenar punteros predecesores en ambas búsquedas. Cuando μ se actualiza a través de algún vértice de cruce x , el algoritmo registra este punto de encuentro y reconstruye la ruta final como el camino hacia adelante de s a x concatenado con el camino hacia atrás de x a t .

La investigación teórica muestra que un enfoque bidireccional optimizado puede ser óptimo para cada instancia, lo que significa que ningún algoritmo correcto puede relajar asintóticamente menos aristas en la misma instancia del grafo. ^{[ 29 ]}

El algoritmo original de Dijkstra puede ampliarse con modificaciones. Por ejemplo, a veces es conveniente presentar soluciones que no sean matemáticamente óptimas. Para obtener una lista clasificada de soluciones subóptimas, primero se calcula la solución óptima. Se elimina del grafo una arista presente en la solución óptima y se calcula la solución óptima para este nuevo grafo. Cada arista de la solución original se suprime sucesivamente y se calcula un nuevo camino más corto. A continuación, las soluciones secundarias se clasifican y se presentan después de la primera solución óptima.

Dijkstra's algorithm is usually the working principle behind link-state routing protocols. OSPF and IS-IS are the most common.

Unlike Dijkstra's algorithm, the Bellman–Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s. The presence of such cycles means that no shortest path can be found, since the label becomes lower each time the cycle is traversed. (This statement assumes that a "path" is allowed to repeat vertices. In graph theory that is normally not allowed. In theoretical computer science it often is allowed.) It is possible to adapt Dijkstra's algorithm to handle negative weights by combining it with the Bellman-Ford algorithm (to remove negative edges and detect negative cycles): Johnson's algorithm.

The A* algorithm is a generalization of Dijkstra's algorithm that reduces the size of the subgraph that must be explored, if additional information is available that provides a lower bound on the distance to the target.

The process that underlies Dijkstra's algorithm is similar to the greedy process used in Prim's algorithm. Prim's purpose is to find a minimum spanning tree that connects all nodes in the graph; Dijkstra is concerned with only two nodes. Prim's does not evaluate the total weight of the path from the starting node, only the individual edges.

Breadth-first search can be viewed as a special-case of Dijkstra's algorithm on unweighted graphs, where the priority queue degenerates into a FIFO queue.

The fast marching method can be viewed as a continuous version of Dijkstra's algorithm which computes the geodesic distance on a triangle mesh.

• Algoritmo de búsqueda A*
• Algoritmo de Bellman-Ford
• Camino euclidiano más corto
• Algoritmo de Floyd-Warshall
• El algoritmo de Johnson
• problema del camino más largo
• Algoritmo de ruta más corta entre todos los pares en paralelo

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Sección 24.3: algoritmo de Dijkstra". Introducción a los algoritmos (Segunda  ed.). Prensa del MIT y McGraw-Hill . págs. 595–601 . ISBN  0-262-03293-7.
• Dial, Robert B. (1969). "Algoritmo 360: Bosque de caminos más cortos con ordenamiento topológico [ H ] " . Communications of the ACM . 12 (11): 632– 633. doi : 10.1145/363269.363610 . S2CID 6754003 . 
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes . 25º Simposio Anual sobre Fundamentos de la Informática. IEEE . págs. 338–346 . doi : 10.1109/SFCS.1984.715934 . 
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" . Journal of the Association for Computing Machinery . 34 (3): 596– 615. doi : 10.1145/28869.28874 . S2CID 7904683 . 
• Zhan, F. Benjamin; Noon, Charles E. (febrero de 1998). "Algoritmos de ruta más corta: una evaluación utilizando redes viales reales". Transportation Science . 32 (1): 65–73 . doi : 10.1287/trsc.32.1.65 . S2CID 14986297 . 
• Leyzorek, M.; Gray, RS; Johnson, AA; Ladew, WC; Meaker, Jr., SR; Petry, RM; Seitz, RN (1957). Investigación de técnicas de modelado – Primer informe anual – 6 de junio de 1956 – 1 de julio de 1957 – Un estudio de técnicas de modelado para sistemas de comunicación . Cleveland, Ohio: Case Institute of Technology.
• Knuth, DE (1977). "Una generalización del algoritmo de Dijkstra". Information Processing Letters . 6 (1): 1– 5. doi : 10.1016/0020-0190(77)90002-3 .
• Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (abril de 1990). "Algoritmos más rápidos para el problema del camino más corto" (PDF) . Journal of the ACM . 37 (2): 213– 223. doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589 . 
• Raman, Rajeev (1997). "Resultados recientes sobre el problema de los caminos más cortos desde una única fuente" . SIGACT News . 28 (2): 81– 87. doi : 10.1145/261342.261352 . S2CID 18031586 . 
• Thorup, Mikkel (2000). "En colas de prioridad de RAM". Revista SIAM de Computación . 30 (1): 86– 109. doi : 10.1137/S0097539795288246 . S2CID 5221089 . 
• Thorup, Mikkel (1999). "Caminos más cortos no dirigidos de una sola fuente con pesos enteros positivos en tiempo lineal" . Journal of the ACM . 46 (3): 362– 394. doi : 10.1145/316542.316548 . S2CID 207654795 . 

• Entrevista de historia oral con Edsger W. Dijkstra , del Instituto Charles Babbage de la Universidad de Minnesota, Minneapolis.
• Implementación del algoritmo de Dijkstra usando TDD , Robert Cecil Martin , The Clean Code Blog