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 gráfico ponderado , que puede representar, por ejemplo, redes de carreteras . Fue concebido por el informático Edsger W. Dijkstra en 1956 y publicado tres años después. [4] [5] [6]
El algoritmo existe en muchas variantes. El algoritmo original de Dijkstra encontró la ruta más corta entre dos nodos dados, [6] pero una variante más común fija un solo nodo como el nodo "fuente" y encuentra las rutas más cortas desde la fuente a todos los demás nodos en el gráfico, produciendo una ruta más corta. árbol .
Para un nodo de origen determinado en el gráfico, el algoritmo encuentra la ruta más corta entre ese nodo y todos los demás. [7] : 196–206 También se puede utilizar para encontrar las rutas más cortas desde un único nodo a un único nodo de destino deteniendo el algoritmo una vez que se ha determinado la ruta más corta al nodo de destino. Por ejemplo, si los nodos del gráfico representan ciudades y los costos de las rutas de borde representan distancias de conducción entre pares de ciudades conectadas por una carretera directa (para simplificar, ignore los semáforos en rojo, las señales de alto, las carreteras de peaje y otras obstrucciones), 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 ampliamente utilizada de algoritmos de ruta más corta son los protocolos de enrutamiento de red , en particular IS-IS (Sistema intermedio a sistema intermedio) y OSPF (Abrir primero la ruta más corta). También se emplea como subrutina en otros algoritmos como el de Johnson .
El algoritmo de Dijkstra utiliza etiquetas que son números enteros positivos o números reales, los cuales están totalmente ordenados . Se puede generalizar el uso de cualquier etiqueta que esté parcialmente ordenada , siempre que las etiquetas posteriores (se produce una etiqueta posterior al atravesar un borde) sean monótonamente no decrecientes. Esta generalización se denomina algoritmo genérico del camino más corto de Dijkstra. [8] [9]
El algoritmo de Dijkstra utiliza una estructura de datos para almacenar y consultar soluciones parciales ordenadas por distancia desde el principio. El algoritmo original de Dijkstra no utiliza una cola de prioridad mínima y se ejecuta en el tiempo (donde está el número de nodos). [10] La idea de este algoritmo también se da en Leyzorek et al. 1957. Fredman y Tarjan 1984 proponen utilizar una cola de prioridad mínima del montón de Fibonacci para optimizar la complejidad del tiempo de ejecución . Este es asintóticamente el algoritmo de ruta más corta de fuente única más rápido conocido para gráficos dirigidos arbitrarios con pesos ilimitados no negativos. Sin embargo, los casos especializados (como pesos acotados/enteros, gráficos acíclicos dirigidos, etc.) pueden mejorarse aún más, como se detalla en Variantes especializadas. Ademá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.
En algunos campos, la inteligencia artificial en particular, el algoritmo de Dijkstra o una variante del mismo se conoce como búsqueda de costos uniformes y se formula como un ejemplo de la idea más general de búsqueda primero el mejor . [11]
¿Cuál es la forma más corta de viajar de Rotterdam a Groningen , en general: de una ciudad determinada a otra ciudad? Es el algoritmo del camino más corto , 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 del café a tomar una taza de café y yo estaba pensando si podía hacer esto, y entonces diseñé el algoritmo para el camino más corto. . Como dije, fue un invento de veinte minutos. De hecho, se publicó en el 59, tres años después. La publicación aún se puede leer y, de hecho, es bastante bonita. Una de las razones por las que es tan bonito es que lo diseñé sin lápiz ni papel. Más tarde supe que una de las ventajas de diseñar sin lápiz ni papel es que casi estás obligado a evitar todas las complejidades evitables. Con el tiempo, ese algoritmo se convirtió, para mi gran asombro, en una de las piedras angulares de mi fama.
— Edsger Dijkstra, en una entrevista con Philip L. Frana, Comunicaciones de la ACM, 2001 [5]
Dijkstra pensó en el problema del camino más corto cuando trabajaba en el Centro de Matemáticas de Ámsterdam en 1956 como programador para demostrar las capacidades de una nueva computadora llamada ARMAC. [12] Su objetivo era elegir tanto un problema como una solución (que sería producida por computadora) que las personas que no usan computadoras pudieran entender. Diseñó el algoritmo de ruta más corta y luego lo implementó para ARMAC para un mapa de transporte ligeramente simplificado de 64 ciudades en los Países Bajos (64, de modo que 6 bits serían suficientes para codificar el número de la ciudad). [5] Un año después, se encontró con otro problema de los ingenieros de hardware que trabajaban en la siguiente computadora del instituto: minimizar la cantidad de cable necesario para conectar las clavijas en el panel posterior de la máquina. Como solución, redescubrió el algoritmo conocido como algoritmo de árbol de expansión mínimo de Prim (conocido anteriormente por Jarník , y también redescubierto por Prim ). [13] [14] Dijkstra publicó el algoritmo en 1959, dos años después de Prim y 29 años después de Jarník. [15] [16]
Dejemos que el nodo en el que comenzamos se llame nodo inicial . Sea la distancia del nodo Y la distancia desde el nodo inicial hasta Y. El algoritmo de Dijkstra comenzará inicialmente con distancias infinitas e intentará mejorarlas paso a paso.
Al planificar una ruta, en realidad no es necesario esperar hasta que el nodo de destino sea "visitado" como se indicó anteriormente: el algoritmo puede detenerse una vez que el nodo de destino tenga la distancia tentativa más pequeña entre todos los nodos "no visitados" (y por lo tanto podría seleccionarse como el siguiente "actual").
Suponga que desea encontrar el camino más corto entre dos intersecciones en un mapa de la ciudad: un punto de partida y un destino . El algoritmo de Dijkstra inicialmente marca la distancia (desde el punto de partida) hasta cada dos intersecciones en el mapa con infinito . Esto no se hace para implicar que haya una distancia infinita, sino para señalar que esas intersecciones aún no han sido visitadas. Algunas variantes de este método dejan las distancias de las intersecciones sin etiquetar . Ahora seleccione la intersección actual en cada iteración. Para la primera iteración, la intersección actual será el punto de partida y la distancia hasta ella (la etiqueta de la intersección) será cero . Para iteraciones posteriores (después de la primera), la intersección actual será la intersección no visitada más cercana al punto de partida (será fácil de encontrar).
Desde la intersección actual, actualice la distancia hasta cada intersección no visitada que esté directamente conectada a ella. Esto se hace determinando la suma de la distancia entre una intersección no visitada y el valor de la intersección actual y luego volviendo a etiquetar la intersección no visitada con este valor (la suma) si es menor que el valor actual de la intersección no visitada. De hecho, la intersección se vuelve a etiquetar si el camino hacia ella a través de la intersección actual es más corto que los caminos conocidos anteriormente. Para facilitar la identificación del camino más corto, marque con lápiz el camino con una flecha que apunte a la intersección reetiquetada si la etiqueta/reetiqueta, y borre todos los demás que apunten hacia ella. Después de haber actualizado las distancias a cada intersección vecina , marque la intersección actual como visitada y seleccione una intersección no visitada con una distancia mínima (desde el punto de partida), o la etiqueta más baja, como la intersección actual. Las intersecciones marcadas como visitadas están etiquetadas con el camino más corto desde el punto de partida hasta ellas y no serán revisadas ni regresadas.
Continúe este proceso de actualizar las intersecciones vecinas con las distancias más cortas, marcando la intersección actual como visitada y pasando a una intersección no visitada más cercana hasta que haya marcado el destino como visitado. Una vez que haya marcado el destino como visitado (como ocurre con cualquier intersección visitada), habrá determinado el camino más corto hasta él desde el punto de partida y podrá trazar su camino de regreso siguiendo las flechas en sentido inverso . En las implementaciones del algoritmo, esto generalmente se hace (después de que el algoritmo ha llegado al nodo de destino) siguiendo a los padres de los nodos desde el nodo de destino hasta el nodo inicial; es por eso que también realizamos un seguimiento del padre de cada nodo.
Este algoritmo no intenta realizar una "exploración" directa hacia el destino como cabría esperar. Más bien, la única consideración para determinar la siguiente intersección "actual" es su distancia desde el punto de partida. Por lo tanto, este algoritmo se expande hacia afuera desde el punto de partida, considerando interactivamente cada nodo que está más cerca en términos de la distancia del camino más corto hasta que llega al destino. Cuando se entiende de esta manera, queda claro cómo el algoritmo necesariamente encuentra el camino más corto. Sin embargo, también puede revelar una de las debilidades del algoritmo: su relativa lentitud en algunas topologías.
En el siguiente algoritmo de pseudocódigo , dist es una matriz que contiene las distancias actuales desde la fuente a otros vértices, es decir, dist[ u ] es la distancia actual desde la fuente al vértice u . La matriz prev contiene punteros a los nodos del salto anterior en la ruta más corta desde el origen hasta el vértice dado (de manera equivalente, es el siguiente salto en la ruta desde el vértice dado hasta la fuente). 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 tiene el menor valor de dist[ u ] . Graph.Edges( u , v ) devuelve la longitud del borde 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 de la ruta desde el nodo raíz al nodo vecino v si pasara por u . Si esta ruta es más corta que la ruta más corta actual registrada para v , esa ruta actual se reemplaza con esta ruta alternativa . [7]
1 función Dijkstra ( Gráfico , fuente ): 2 3 para cada vértice v en Graph.Vertices : 4 dist[ v ] ← INFINITO 5 anterior[ v ] ← INDEFINIDO 6 agregue v a Q 7 dist[ fuente ] ← 0 8 9 mientras Q no esté vacío:10 u ← vértice en Q con min dist[u]11 eliminarte de Q12 13 para cada vecino v de u todavía en Q :14 alt ← dist[ u ] + Graph.Edges( u , v )15 si alt < dist[ v ]:16 dist[ v ] ← alt 17 anterior[ v ] ← u1819 devolver dist[], anterior[]
Si sólo estamos interesados en un camino más corto entre los vértices fuente y destino , podemos terminar la búsqueda después de la línea 10 si u = destino . Ahora podemos leer la ruta más corta desde el origen al destino mediante iteración inversa:
1 S ← secuencia vacía2 u ← objetivo 3 si prev[ u ] está definido o u = fuente : // Haz algo solo si el vértice es alcanzable 4 mientras u está definido: // Construye la ruta más corta con una pila S 5 inserta u al comienzo de S // Empuja el vértice en la pila 6 u ← prev[ u ] // Atraviesa desde el objetivo hasta el origen
Ahora la secuencia S es la lista de vértices que constituyen uno de los caminos más cortos desde el origen al destino , o la secuencia vacía si no existe ningún camino.
Un problema más general sería encontrar todos los caminos más cortos entre el origen y el destino (puede haber varios diferentes de la misma longitud). Luego, en lugar de almacenar solo un nodo en cada entrada de prev[] , almacenaríamos todos los nodos que cumplan la condición de relajación. Por ejemplo, si tanto r como el origen se conectan al destino y ambos se encuentran en caminos más cortos diferentes a través del destino (porque el costo del borde es el mismo en ambos casos), entonces agregaríamos tanto r como el origen a prev[ destino ] . Cuando se completa el algoritmo, la estructura de datos anterior[] en realidad describirá un gráfico que es un subconjunto del gráfico original al que se le han eliminado algunos bordes. Su propiedad clave será que si el algoritmo se ejecutó con algún nodo inicial, entonces cada ruta desde ese nodo a cualquier otro nodo en el nuevo gráfico será la ruta más corta entre esos nodos en el gráfico original, y todas las rutas de esa longitud desde el gráfico original estará presente en el nuevo gráfico. Luego, para encontrar todos estos caminos más cortos entre dos nodos dados, usaríamos un algoritmo de búsqueda de caminos en el nuevo gráfico, como la búsqueda en profundidad .
Una cola de prioridad mínima es un tipo de datos abstracto que proporciona 3 operaciones básicas: add_with_priority() , decrement_priority() y extract_min() . Como se mencionó anteriormente, el uso de una estructura de datos de este tipo puede generar tiempos de computación más rápidos que el uso de una cola básica. En particular, el montón de Fibonacci [18] o la cola de Brodal ofrecen implementaciones óptimas para esas 3 operaciones. Como el algoritmo es ligeramente diferente, se menciona aquí, también en pseudocódigo:
1 función Dijkstra ( Gráfico , fuente ):2 dist[ fuente ] ← 0 // Inicialización34 crear cola de prioridad de vértice Q56 para cada vértice v en Graph.Vertices :7 if v ≠ fuente 8 dist[ v ] ← INFINITY // Distancia desconocida desde la fuente a v 9 prev[ v ] ← UNDEFINED // Predecesor de v1011 P .add_with_priority( v , dist[ v ])121314 mientras Q no está vacío: // El bucle principal 15 u ← Q .extract_min() // Elimina y devuelve el mejor vértice 16 para cada vecino v de u : // Revisa todos los v vecinos de u 17 alt ← dist[ u ] + Gráfico.Edges( u , v )18 si alt < dist[ v ]:19 dist[ v ] ← alt 20 prev[ v ] ← u 21 Q .decrease_priority( v , alt )2223 retorno dist, anterior
En lugar de llenar la cola de prioridad con todos los nodos en la fase de inicialización, también es posible inicializarla para que contenga solo fuente ; luego, dentro del bloque, disminuir_prioridad() se convierte en una operación add_with_priority() si el nodo aún no está en la cola. [7] : 198 if alt < dist[v]
Otra alternativa más es agregar nodos incondicionalmente a la cola de prioridad y, en su lugar, verificar después de la extracción que no esté volviendo a visitarlos o que aún no se haya encontrado una conexión más corta. Esto se puede hacer extrayendo adicionalmente la prioridad asociada pde la cola y procesando solo más dentro del bucle. [19]if p == dist[u]while Q is not empty
Estas alternativas pueden utilizar colas de prioridad completamente basadas en matrices sin funcionalidad de clave de disminución, que se ha descubierto que logran tiempos de computación aún más rápidos en la práctica. Sin embargo, se encontró que la diferencia en el rendimiento era menor para gráficos más densos. [20]
La prueba del algoritmo de Dijkstra se construye mediante inducción sobre el número de nodos visitados.
Hipótesis invariante : para cada nodo visitado v , es la distancia más corta desde la fuente hasta v , y para cada nodo no visitado u , es la distancia más corta desde la fuente hasta u cuando se viaja solo a través de nodos visitados, o infinito si no existe tal camino. (Nota: no asumimos que sea la distancia más corta real para los nodos no visitados, mientras que sí es la distancia más corta real)dist[v]dist[u]dist[u]dist[v]
El caso base es cuando solo hay un nodo visitado, es decir, el nodo fuente inicial , en cuyo caso la hipótesis es trivial .
A continuación, asuma la hipótesis para k-1 nodos visitados. A continuación, elegimos u como el siguiente nodo visitado según el algoritmo. Afirmamos que es la distancia más corta desde la fuente hasta u .dist[u]
Para probar esa afirmación, procederemos con una prueba por contradicción. Si hubiera una ruta más corta, entonces puede haber dos casos: la ruta más corta contiene otro nodo no visitado o no.
En el primer caso, sea w el primer nodo no visitado en el camino más corto. Según la hipótesis de inducción, el camino más corto desde la fuente hasta u y w a través del nodo visitado solo tiene costo y respectivamente. Eso significa que el costo de pasar de la fuente a u a través de w tiene el costo de al menos + el costo mínimo de pasar de w a u . Como los costos marginales son positivos, el costo mínimo de pasar de w a u es un número positivo.dist[u]dist[w]dist[w]
También dist[u] < dist[w]porque el algoritmo eligió u en lugar de w .
Ahora llegamos a una contradicción que dist[u] < dist[w]todavía dist[w]+ un número positivo < dist[u].
En el segundo caso, sea w el penúltimo nodo en el camino más corto. Eso significa . Esto es una contradicción porque cuando se visita w , debería haberse fijado como máximo en . dist[w] + Graph.Edges[w,u] < dist[u]dist[u]dist[w] + Graph.Edges[w,u]
Para todos los demás nodos visitados v , la hipótesis de inducción nos dijo que ya es la distancia más corta desde la fuente , y el paso del algoritmo no cambia eso.dist[v]
Después de procesar u, seguirá siendo cierto que para cada nodo visitado w , será la distancia más corta desde el origen hasta w usando los nodos visitados solo porque si hubiera una ruta más corta que no pasara por u , la habríamos encontrado previamente, y si hubiera una ruta más corta usando u, la habríamos actualizado al procesar u .dist[w]
Una vez visitados todos los nodos, la ruta más corta desde el origen a cualquier nodo v consta únicamente de los nodos visitados y, por lo tanto, es la distancia más corta.dist[v]
Los límites del tiempo de ejecución del algoritmo de Dijkstra en un gráfico con aristas E y vértices V se pueden expresar como una función del número de aristas, denotadas , y el número de vértices, denotados , usando notación O grande . 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 son para cualquier gráfico simple, pero esa simplificación ignora el hecho de que en algunos problemas, otros límites superiores pueden ser válidos.
Para cualquier estructura de datos para el conjunto de vértices Q , el tiempo de ejecución está en [2]
donde y son las complejidades de las operaciones de disminución clave y extracción mínima en Q , respectivamente.
La versión más simple del algoritmo de Dijkstra almacena el conjunto de vértices Q como una lista o matriz enlazada, y los bordes como una lista o matriz de adyacencia . En este caso, extraer 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 .
Para gráficos dispersos , es decir, gráficos con muchos menos bordes, el algoritmo de Dijkstra se puede implementar de manera más eficiente almacenando el gráfico en forma de listas de adyacencia y usando un árbol de búsqueda binario autoequilibrado , un montón binario , un montón de emparejamiento o un montón de Fibonacci. como cola de prioridad para implementar la extracción mínima de manera eficiente. Para realizar pasos de clave de disminución en un montón binario de manera eficiente, es necesario utilizar una estructura de datos auxiliar que asigne cada vértice a su posición en el montón y mantener esta estructura actualizada a medida que cambia la cola de prioridad Q. Con un árbol de búsqueda binario o un montón binario autoequilibrado, el algoritmo requiere
tiempo en el peor de los casos; para gráficos conectados, este límite de tiempo se puede simplificar a . El montón de Fibonacci mejora esto a
Cuando se utilizan montones binarios, la complejidad del tiempo de caso promedio es menor que en el peor de los casos: suponiendo que los costos de borde se extraen independientemente de una distribución de probabilidad común , el número esperado de operaciones de clave de disminución está limitado por , lo que da un tiempo de ejecución total de [7 ] : 199–200
En presentaciones comunes del algoritmo de Dijkstra, inicialmente todos los nodos se ingresan en la cola de prioridad. Sin embargo, esto no es necesario: el algoritmo puede comenzar con una cola de prioridad que contenga solo un elemento e insertar nuevos elementos a medida que se descubren (en lugar de hacer una disminución de clave, verifique si la clave está en la cola; si es decir, disminuya su clave; en caso contrario, insértela). [7] : 198 Esta variante tiene los mismos límites en el peor de los casos que la variante común, pero mantiene una cola de prioridad más pequeña en la práctica, lo que acelera las operaciones de la cola. [11]
Además, no insertar todos los nodos en un gráfico hace posible extender el algoritmo para encontrar la ruta más corta desde una única fuente hasta el más cercano de un conjunto de nodos objetivo en gráficos infinitos o aquellos que son demasiado grandes para representarlos en la memoria. El algoritmo resultante se denomina búsqueda de costo uniforme (UCS) en la literatura sobre inteligencia artificial [11] [21] [22] y se puede expresar en pseudocódigo como
El procedimiento uniform_cost_search(inicio) es nodo ← inicio frontera ← cola de prioridad que contiene solo el nodo expandido ← conjunto vacío hazlo si la frontera está vacía y luego regresa el fracaso nodo ← frontera.pop() si el nodo es un estado objetivo, entonces devuelve la solución (nodo) expandido.agregar(nodo) para cada uno de los vecinos del nodo n, hagalo si n no está expandido ni en la frontera, entonces frontier.add( n ) de lo contrario, si n está en la frontera con un costo más alto reemplazar el nodo existente con n
La complejidad de este algoritmo se puede expresar de una manera alternativa para gráficos muy grandes: cuando C * es la longitud del camino más corto desde el nodo inicial hasta cualquier nodo que satisfaga el predicado "objetivo", cada borde ha costado al menos ε , y el número de vecinos por nodo está limitado por b , entonces la complejidad temporal y espacial del peor de los casos del algoritmo están en O ( b 1+⌊ C * ⁄ ε ⌋ ) . [21]
Otras optimizaciones del algoritmo de Dijkstra para el caso de un solo objetivo incluyen variantes bidireccionales , variantes dirigidas a objetivos como el algoritmo A* (ver § Problemas y algoritmos relacionados), poda de gráficos para determinar qué nodos es probable que formen el segmento medio de los caminos más cortos. (enrutamiento basado en alcance) y descomposiciones jerárquicas del gráfico de entrada que reducen el enrutamiento s – t para conectar s y t a sus respectivos " nodos de tránsito ", seguido del cálculo de la ruta más corta entre estos nodos de tránsito utilizando una "autopista". [23] Es posible que se necesiten combinaciones de tales técnicas para lograr un desempeño práctico óptimo en problemas específicos. [24]
Cuando los pesos de los arcos son enteros pequeños (limitados por un parámetro ), se pueden utilizar colas especializadas que aprovechan este hecho para acelerar el algoritmo de Dijkstra. El primer algoritmo de este tipo fue el algoritmo de Dial (Dial 1969) para gráficos con pesos de borde enteros positivos, que utiliza una cola de cubo para obtener un tiempo de ejecución . El uso de un árbol de Van Emde Boas como cola de prioridad aumenta la complejidad (Ahuja et al. 1990). Otra variante interesante basada en una combinación de un nuevo montón de base y el conocido montón de Fibonacci se ejecuta en el tiempo (Ahuja et al. 1990). Finalmente, los mejores algoritmos en este caso especial son los siguientes. El algoritmo dado por (Thorup 2000) se ejecuta en el tiempo y el algoritmo dado por (Raman 1997) se ejecuta en el tiempo.
La funcionalidad del algoritmo original de Dijkstra se puede ampliar con una variedad de modificaciones. Por ejemplo, a veces es deseable presentar soluciones que no son matemáticamente óptimas. Para obtener una lista clasificada de soluciones no óptimas, primero se calcula la solución óptima. Se elimina del gráfico un único borde que aparece en la solución óptima y se calcula la solución óptima para este nuevo gráfico. Cada borde de la solución original se suprime a su vez y se calcula una nueva ruta más corta. Luego, las soluciones secundarias se clasifican y se presentan después de la primera solución óptima.
El algoritmo de Dijkstra suele ser el principio de funcionamiento detrás de los protocolos de enrutamiento de estado de enlace , siendo OSPF e IS-IS los más comunes.
A diferencia del algoritmo de Dijkstra, el algoritmo de Bellman-Ford se puede utilizar en gráficos con pesos de borde negativos, siempre que el gráfico no contenga ningún ciclo negativo accesible desde el vértice fuente s . La presencia de tales ciclos significa que no existe un camino más corto, ya que el peso total disminuye cada vez que se recorre el ciclo. (Esta afirmación supone que un "camino" puede repetir vértices. En teoría de grafos eso normalmente no está permitido. En informática teórica a menudo está permitido). Es posible adaptar el algoritmo de Dijkstra para manejar aristas de peso negativos combinándolo con el algoritmo Bellman-Ford (para eliminar bordes negativos y detectar ciclos negativos); dicho algoritmo se llama algoritmo de Johnson .
El algoritmo A* es una generalización del algoritmo de Dijkstra que reduce el tamaño del subgrafo que debe explorarse, si hay información adicional disponible que proporcione un límite inferior en la "distancia" al objetivo.
El proceso que subyace al algoritmo de Dijkstra es similar al proceso codicioso utilizado en el algoritmo de Prim . El propósito de Prim es encontrar un árbol de expansión mínimo que conecte todos los nodos del gráfico; A Dijkstra sólo le preocupan dos nodos. Prim's no evalúa el peso total del camino desde el nodo inicial, solo los bordes individuales.
La búsqueda en amplitud puede verse como un caso especial del algoritmo de Dijkstra en gráficos no ponderados, donde la cola de prioridad degenera en una cola FIFO.
El método de marcha rápida puede verse como una versión continua del algoritmo de Dijkstra que calcula la distancia geodésica en una malla triangular.
Desde el punto de vista de la programación dinámica , el algoritmo de Dijkstra es un esquema de aproximación sucesiva que resuelve la ecuación funcional de programación dinámica para el problema del camino más corto mediante el método Reaching . [25] [26] [27]
De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, [28] es decir
Problema 2. Encuentre el camino de longitud total mínima entre dos nodos dados y .
Usamos el hecho de que, si es un nodo en el camino mínimo desde hasta , el conocimiento de este último implica el conocimiento del camino mínimo desde hasta .
es una paráfrasis del famoso Principio de Optimidad de Bellman en el contexto del problema del camino más corto.
En el Centro de Matemáticas un proyecto importante fue la construcción de la computadora ARMAC.
Para su inauguración oficial en 1956, Dijkstra ideó un programa para resolver un problema interesante para un público no técnico: Dada una red de caminos que conectan ciudades, ¿cuál es la ruta más corta entre dos ciudades designadas?
El tercer algoritmo clásico de árbol de expansión mínima fue descubierto por Jarník y redescubierto por Prim y Dikstra;
se le conoce comúnmente como algoritmo de Prim.
