Algoritmo de Dijkstra

Algoritmo para encontrar caminos más cortos

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, redes 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} También se puede utilizar para encontrar la ruta más corta a un nodo de destino específico, terminando el algoritmo una vez que se conoce la ruta más corta al nodo de destino. Por ejemplo, si los nodos del gráfico representan ciudades y los costos de los bordes representan las distancias promedio entre pares de ciudades conectadas por una carretera directa, entonces el algoritmo de Dijkstra se puede utilizar 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 , más notablemente IS-IS (Intermediate System to Intermediate System) y OSPF (Open Shortest Path First). También se emplea como subrutina en otros 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 un tiempo , donde es el número de nodos. ^[8] La idea de este algoritmo también se da en Leyzorek et al. 1957. Fredman y Tarjan 1984 propusieron usar una cola de prioridad de montón de Fibonacci para optimizar la complejidad del tiempo de ejecución a . Este es asintóticamente el algoritmo de ruta más corta de fuente única más rápido conocido para grafos dirigidos arbitrarios con pesos no negativos ilimitados. Sin embargo, los casos especializados (como pesos acotados/enteros, grafos 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. ${\displaystyle \Theta (|V|^{2})}$ ${\displaystyle |V|}$ ${\displaystyle \Theta (|E|+|V|\log |V|)}$

El algoritmo de Dijkstra se utiliza habitualmente en gráficos en los que los pesos de las aristas son números enteros positivos o reales. Se puede generalizar a cualquier gráfico en el que los pesos de las aristas estén parcialmente ordenados , siempre que las etiquetas posteriores (se produce una etiqueta posterior al atravesar una arista) sean monótonamente no decrecientes. ^{[9] [10]}

En muchos campos, particularmente en la inteligencia artificial , el algoritmo de Dijkstra o una variante del mismo se conoce como búsqueda de costo uniforme y se formula como un ejemplo de la idea más general de búsqueda del mejor primero . ^[11]

Historia

¿Cuál es el camino más corto para viajar de Rotterdam a Groningen , en general: de una ciudad dada a otra ciudad dada? 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 de la cafetería a tomar una taza de café y yo estaba pensando si podría hacerlo, y entonces diseñé el algoritmo del camino más corto. Como dije, fue una invención de veinte minutos. De hecho, se publicó en el 59, tres años después. La publicación todavía se puede leer, es, de hecho, bastante agradable. Una de las razones por las que es tan agradable fue que lo diseñé sin lápiz y papel. Más tarde supe que una de las ventajas de diseñar sin lápiz y papel es que te ves casi obligado a evitar todas las complejidades evitables. Al final, 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 no informáticas pudieran entender. Diseñó el algoritmo del camino más corto 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 próxima computadora del instituto: minimizar la cantidad de cable necesario para conectar los pines 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]}

Algoritmo

Ilustración del algoritmo de Dijkstra que encuentra una ruta desde un nodo de inicio (abajo a la izquierda, rojo) hasta un nodo de destino (arriba a la derecha, verde) en un problema de planificación del movimiento de un robot . Los nodos abiertos representan el conjunto "tentativo" (también conocido como el conjunto de nodos "no visitados"). Los nodos llenos son los visitados, y el color representa la distancia: cuanto más verde, más cerca. Los nodos en todas las direcciones se exploran de manera uniforme y aparecen más o menos como un frente de onda circular , ya que el algoritmo de Dijkstra utiliza una heurística de elegir la ruta más corta conocida hasta el momento.

Elijamos un nodo inicial y dejemos que la distancia del nodo N sea la distancia desde el nodo inicial a N. El algoritmo de Dijkstra comenzará inicialmente con distancias infinitas e intentará mejorarlas paso a paso.

1. Marcar todos los nodos como no visitados. Crear un conjunto de todos los nodos no visitados denominado conjunto no visitado .
2. Asignar a cada nodo una distancia desde el punto de partida: para el nodo de partida, 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 del algoritmo, la distancia de un nodo N es la longitud del camino más corto descubierto hasta el momento entre el nodo de partida y N . ^[17]
3. Del conjunto no visitado, seleccione el nodo actual que tenga la distancia finita más pequeña; inicialmente, este será el nodo de inicio, que tiene una distancia cero. Si el conjunto no visitado está vacío o contiene solo nodos con una distancia infinita (que son inalcanzables), entonces el algoritmo termina yendo al paso 6. Si solo nos interesa la ruta a un nodo de destino, podemos terminar aquí si el nodo actual es el nodo de destino. De lo contrario, podemos continuar buscando las rutas más cortas a todos los nodos alcanzables.
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 asignada actualmente al vecino y asígnele la más pequeña. Por ejemplo, si el nodo actual A está marcado con una distancia de 6 y el borde 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 estaba marcado previamente con una distancia mayor que 8, actualícelo a 8 (la ruta a B a través de A es más corta). De lo contrario, mantenga su distancia actual (la ruta a B a través de A no es la más corta).
5. Cuando terminemos de considerar todos los vecinos no visitados del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto de no visitados. Esto es para que nunca más se verifique un nodo visitado, lo cual es correcto porque la distancia registrada en el nodo actual es mínima (como se aseguró en el paso 3) y, por lo tanto, definitiva. Vuelva al paso 3.
6. Una vez que el bucle sale (pasos 3 a 5), ​​cada nodo visitado contendrá su distancia más corta desde el nodo inicial.

Descripción

Supongamos que desea encontrar el camino más corto entre dos intersecciones en un mapa de una ciudad: un punto de partida y un destino . El algoritmo de Dijkstra inicialmente marca la distancia (desde el punto de partida) a cada otra intersección en el mapa con infinito . Esto se hace no para implicar que hay una distancia infinita, sino para notar 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 él (la etiqueta de la intersección) será cero . Para las iteraciones posteriores (después de la primera), la intersección actual será la intersección no visitada más cercana al punto de partida (esto será fácil de encontrar).

Desde la intersección actual, actualice la distancia a cada intersección no visitada que esté conectada directamente con 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. En efecto, 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 previamente. Para facilitar la identificación del camino más corto, marque con lápiz la carretera con una flecha que apunte a la intersección reetiquetada si la etiqueta/reetiqueta, y borre todas las demás que apunten a 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 la distancia mínima (desde el punto de partida) - o la etiqueta más baja - como la intersección actual. Las intersecciones marcadas como visitadas se etiquetan con el camino más corto desde el punto de partida hasta ella y no se volverán a visitar ni a regresar a ellas.

Continúe este proceso de actualización de las intersecciones vecinas con las distancias más cortas, marcando la intersección actual como visitada y pasando a la 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 es el caso con cualquier intersección visitada), habrá determinado el camino más corto hacia él desde el punto de partida y podrá rastrear 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 haya llegado al nodo de destino) siguiendo los padres de los nodos desde el nodo de destino hasta el nodo de inicio; 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 se podrí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 distancia de ruta más corta hasta que llega al destino. Cuando se entiende de esta manera, queda claro cómo el algoritmo necesariamente encuentra la ruta más corta. Sin embargo, también puede revelar una de las debilidades del algoritmo: su relativa lentitud en algunas topologías.

Pseudocódigo

En el siguiente pseudocódigo , dist es una matriz que contiene las distancias actuales desde la fuente hasta otros vértices, es decir, dist[ u ] es la distancia actual desde la fuente hasta el vértice u . La matriz prev contiene punteros a nodos de salto anterior en la ruta más corta desde la fuente hasta el vértice dado (equivalentemente, es el siguiente salto en la ruta desde el vértice dado hasta la fuente). El código u ← vertex in 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.Edges( 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 de la ruta desde el nodo fuente hasta el nodo vecino v si pasara por u . Si esta ruta es más corta que la ruta más corta actual registrada para v , entonces la distancia de v se actualiza a alt . ^[7]

Una demostración del algoritmo de Dijkstra basado en la distancia euclidiana. Las líneas rojas son el camino más corto que cubre, es decir, conectando u y prev[ u ]. Las líneas azules indican dónde ocurre la relajación, es decir, conectando v con un nodo u en Q , lo que da un camino más corto desde la fuente hasta v .

1 función Dijkstra( Gráfico , fuente ): 2  3 para cada vértice v en Graph.Vertices : 4 dist[ v ] ← INFINITO 5 prev[ v ] ← INDEFINIDO 6 suma v a Q 7 dist[ fuente ] ← 0 8  9 mientras  Q no esté vacío:10 u ← vértice en Q con mínima dist[u]11 eliminar u 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 prev[ v ] ← u1819 devuelve dist[], prev[]

Si solo nos interesa la ruta más corta entre los vértices origen y destino , podemos finalizar la búsqueda después de la línea 10 si u = destino . Ahora podemos leer la ruta más corta desde el origen hasta el destino mediante iteración inversa:

1 S ← secuencia vacía2 u ← objetivo
3 si prev[ u ] está definido o  u = origen : // Hacer algo solo si el vértice es alcanzable
4 mientras  u esté definido: // Construir la ruta más corta con una pila S
5 insertar u al comienzo de S  // Empujar el vértice en la pila
6 u ← prev[ u ] // Recorrer desde el objetivo hasta el origen

Ahora bien, la secuencia S es la lista de vértices que constituyen uno de los caminos más cortos desde el origen hasta el 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). Entonces, en lugar de almacenar solo un único nodo en cada entrada de prev[], almacenaríamos todos los nodos que satisfacen la condición de relajación. Por ejemplo, si tanto r como el origen se conectan al destino y ambos se encuentran en diferentes caminos más cortos a través del destino (porque el costo de borde es el mismo en ambos casos), entonces agregaríamos tanto r como el origen a prev[ target ] . Cuando el algoritmo se complete, la estructura de datos prev[] en realidad describirá un gráfico que es un subconjunto del gráfico original con algunos bordes eliminados. Su propiedad clave será que si el algoritmo se ejecutó con algún nodo de inicio, entonces cada camino desde ese nodo a cualquier otro nodo en el nuevo gráfico será el camino más corto entre esos nodos en el gráfico original, y todos los caminos de esa longitud desde el gráfico original estarán presentes en el nuevo gráfico. Luego, para encontrar todos estos caminos más cortos entre dos nodos dados, utilizaríamos un algoritmo de búsqueda de rutas en el nuevo gráfico, como una búsqueda en profundidad .

Usando una cola de prioridad

Una cola de prioridad mínima es un tipo de datos abstracto que proporciona tres operaciones básicas: add_with_priority() , decrease_priority() y extract_min() . Como se mencionó anteriormente, el uso de una estructura de datos de este tipo puede generar tiempos de procesamiento más rápidos que el uso de una cola básica. En particular, el montículo de Fibonacci ^[18] o la cola de Brodal ofrecen implementaciones óptimas para esas tres operaciones. Como el algoritmo es ligeramente diferente en apariencia, se menciona aquí, también en pseudocódigo:

1 función Dijkstra( Gráfico , fuente ):2 crear cola de prioridad de vértices Q34 dist[ source ] ← 0 // Inicialización
5 Q .add_with_priority( source , 0) // La prioridad asociada es igual a dist[·]67 para cada vértice v en Graph.Vertices :8 si  v ≠ fuente
9 prev[ v ] ← INDEFINIDO // Predecesor de v
10 dist[ v ] ← INFINITO // Distancia desconocida desde la fuente hasta v11 Q.add_with_priority(v, INFINITO)121314 mientras  Q no esté vacío: // El bucle principal
15 u ← Q .extract_min() // Eliminar y devolver el mejor vértice
16 para cada vecino v de u : // Recorrer todos los v vecinos de u
17 alt ← dist[ u ] + Graph.Edges( u , v )18 si  alt < dist[ v ]:19 prev[ v ] ← u
20 dist[ v ] ← alt
21 Q .decrease_priority( v , alt )2223 retorno dist, prev

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 el origen ; luego, dentro del bloque, la operación decrease_priority() 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 es agregar nodos incondicionalmente a la cola de prioridad y, en su lugar, verificar después de la extracción ( ) que no se esté volviendo a visitar, o que aún no se haya encontrado una conexión más corta en el bloque. Esto se puede hacer extrayendo adicionalmente la prioridad asociada de la cola y solo procesando más dentro del bucle. ^[19]u ← Q.extract_min()if alt < dist[v]pif p == dist[u]while Q is not empty

Estas alternativas pueden utilizar colas de prioridad basadas completamente en matrices sin la funcionalidad de clave decreciente, que se ha comprobado que logran tiempos de computación incluso más rápidos en la práctica. Sin embargo, se ha comprobado que la diferencia en el rendimiento es menor para gráficos más densos. ^[20]

Prueba de corrección

Para demostrar la exactitud del algoritmo de Dijkstra, procedemos por inducción matemática sobre el número de nodos visitados. ^[21]

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 es la distancia más corta real para los nodos no visitados, mientras que es la distancia más corta real)dist[v]dist[u]dist[u]dist[v]

Caso base :

El caso base es cuando solo hay un nodo visitado, source . Su distancia se define como cero, que es la distancia más corta, ya que no se permiten pesos negativos. Por lo tanto, la hipótesis se cumple.

Paso inductivo :

Supongamos que la hipótesis es válida para los nodos visitados. Queremos demostrar que es válida para los nodos. Sea u el siguiente nodo visitado según el algoritmo, es decir, el nodo con el mínimo . Afirmamos que es la distancia más corta desde la fuente hasta u . ${\displaystyle k}$ ${\displaystyle k+1}$dist[u]dist[u]

Para demostrar esta afirmación, procedemos por contradicción. Si hubiera un camino más corto, entonces este camino más corto o bien contiene otro nodo no visitado o no.

• En el primer caso, sea w el primer nodo no visitado en esta ruta más corta. Por la hipótesis de inducción, las rutas más cortas desde la fuente hasta u y w a través de los nodos visitados solo tienen costos y respectivamente. Esto significa que el costo de ir desde la fuente hasta u vía w tiene el costo de al menos + el costo mínimo de ir desde w hasta u . Como los costos de borde son positivos, el costo mínimo de ir desde w hasta u es un número positivo. Sin embargo, es como máximo porque de lo contrario w habría sido elegido por la cola de prioridad en lugar de v. Esto es una contradicción, ya que ya se ha establecido que + un número positivo < .dist[u]dist[w]dist[w]dist[u]dist[w]dist[w]dist[u]

• En el último caso, sea w el penúltimo nodo en la ruta más corta. Esto significa que . Esto es una contradicción porque para cuando se visita w , debería haberse establecido en como máximo .dist[w] + Graph.Edges[w,u] < dist[u]dist[u]dist[w] + Graph.Edges[w,u]

Para todos los demás nodos visitados v , ya se sabe que es la distancia más corta desde la fuente , debido a la hipótesis inductiva, y estos valores no cambian.dist[v]

Después de procesar u , seguirá siendo cierto que para cada nodo no visitado w , será la distancia más corta desde la fuente hasta w utilizando solo los nodos visitados. Si hubiera una ruta más corta que no utilizara u , la habríamos encontrado previamente, y si hubiera una ruta más corta que utilizara u , la habríamos actualizado al procesar u .dist[w]

Una vez visitados todos los nodos, la ruta más corta desde el origen hasta cualquier nodo v consta únicamente de los nodos visitados. Por lo tanto, es la distancia más corta.dist[v]

Duración del programa

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 como , y el número de vértices, denotado como , utilizando la notación big-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 es para cualquier grafo simple, pero esa simplificación no tiene en cuenta el hecho de que en algunos problemas, pueden cumplirse otros límites superiores en . ${\displaystyle |E|}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle O(|V|^{2})}$ ${\displaystyle |E|}$

Para cualquier estructura de datos para el conjunto de vértices Q , el tiempo de ejecución está en ^[2]

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

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

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 o matriz de adyacencia . En este caso, extract-minimum 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 . ${\displaystyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}$

Para los gráficos dispersos , es decir, los gráficos con muchos menos que aristas, el algoritmo de Dijkstra se puede implementar de manera más eficiente almacenando el gráfico en forma de listas de adyacencia y utilizando un árbol binario de búsqueda 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 del mínimo de manera eficiente. Para realizar pasos de clave decreciente 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 binario de búsqueda autoequilibrado o un montón binario, el algoritmo requiere ${\displaystyle |V|^{2}}$

${\displaystyle \Theta ((|E|+|V|)\log |V|)}$

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 ${\displaystyle \Theta (|E|\log |V|)}$

${\displaystyle \Theta (|E|+|V|\log |V|).}$

Al utilizar montones binarios, la complejidad temporal del 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 disminución de clave está limitado por , lo que da un tiempo de ejecución total de ^{[7] : 199–200} ${\displaystyle \Theta (|V|\log(|E|/|V|))}$

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

Optimizaciones prácticas y gráficos infinitos

En las presentaciones comunes del algoritmo de Dijkstra, inicialmente todos los nodos se introducen en la cola de prioridad. Sin embargo, esto no es necesario: el algoritmo puede comenzar con una cola de prioridad que contiene solo un elemento e ir insertando nuevos elementos a medida que se descubren (en lugar de hacer una disminución de clave, comprobar si la clave está en la cola; si lo está, disminuir su clave, en caso contrario insertarla). ^{[7] : 198} Esta variante tiene los mismos límites de peor caso que la variante común, pero mantiene una cola de prioridad más pequeña en la práctica, acelerando las operaciones de cola. ^[11]

Además, no insertar todos los nodos en un grafo permite extender el algoritmo para encontrar la ruta más corta desde una única fuente hasta el más cercano de un conjunto de nodos de destino en grafos infinitos o aquellos demasiado grandes para ser representados en la memoria. El algoritmo resultante se denomina búsqueda de costo uniforme (UCS) en la literatura de inteligencia artificial ^{[11] [22] [23]} y se puede expresar en pseudocódigo como

El procedimiento uniform_cost_search(start) es nodo ← inicio frontera ← cola de prioridad que contiene solo el nodo expandido ← conjunto vacío ¿Qué hacer  si la frontera está vacía y luego  devolver el error? nodo ← frontera.pop() Si el nodo es un estado objetivo , entonces  devuelve solución(nodo) expandido.add(nodo) para cada uno de los vecinos n del nodo, si  n  no está en la expansión y no está en la frontera, entonces frontier.add( n ) de lo contrario, si  n está en la frontera con un costo mayor Reemplazar el nodo existente por 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 tiene un costo al menos ε , y el número de vecinos por nodo está limitado por b , entonces la complejidad temporal y espacial del peor caso del algoritmo están ambas en O ( b ^{1+⌊ C * ⁄ ε ⌋} ) . ^[22]

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 grafos para determinar qué nodos tienen más probabilidades de formar el segmento medio de las rutas más cortas (enrutamiento basado en alcance) y descomposiciones jerárquicas del grafo de entrada que reducen el enrutamiento s – t para conectar s y t con sus respectivos " nodos de tránsito " seguido por el cálculo de la ruta más corta entre estos nodos de tránsito utilizando una "autopista". ^[24] Es posible que se necesiten combinaciones de dichas técnicas para lograr un rendimiento práctico óptimo en problemas específicos. ^[25]

Variantes especializadas

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 grafos con pesos de aristas enteros positivos, que utiliza una cola de cubos para obtener un tiempo de ejecución . El uso de un árbol de Van Emde Boas como cola de prioridad lleva la complejidad a (Ahuja et al. 1990). Otra variante interesante basada en una combinación de un nuevo montón de radix 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. ${\displaystyle C}$ ${\displaystyle O(|E|+|V|C)}$ ${\displaystyle O(|E|\log \log C)}$ ${\displaystyle O(|E|+|V|{\sqrt {\log C}})}$ ${\displaystyle O(|E|\log \log |V|)}$ ${\displaystyle O(|E|+|V|\min\{(\log |V|)^{1/3+\varepsilon },(\log C)^{1/4+\varepsilon }\})}$

Problemas y algoritmos relacionados

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 sean matemáticamente óptimas. Para obtener una lista ordenada de soluciones no óptimas, primero se calcula la solución óptima. Se elimina del gráfico una única arista que aparezca en la solución óptima y se calcula la solución óptima para este nuevo gráfico. Se suprimen a su vez todas las aristas de la solución original y se calcula una nueva ruta más corta. Luego, se ordenan y presentan las soluciones secundarias 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 Bellman-Ford se puede utilizar en grafos con pesos de arista negativos, siempre que el grafo no contenga ningún ciclo negativo al que se pueda llegar desde el vértice de origen s . La presencia de tales ciclos significa que no hay un camino más corto, ya que el peso total se vuelve menor cada vez que se recorre el ciclo. (Esta afirmación supone que se permite un "camino" para repetir vértices. En la teoría de grafos, eso normalmente no está permitido. En la informática teórica, a menudo se permite). Es posible adaptar el algoritmo de Dijkstra para manejar aristas de peso negativo combinándolo con el algoritmo Bellman-Ford (para eliminar aristas negativas 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 subgráfico que se debe explorar, 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 voraz utilizado en el algoritmo de Prim . El objetivo de Prim es encontrar un árbol de expansión mínimo que conecte todos los nodos del gráfico; Dijkstra se ocupa únicamente de dos nodos. El algoritmo de Prim no evalúa el peso total de la ruta desde el nodo inicial, sino 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.

Perspectiva de programación dinámica

Desde un punto de vista de 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 de la ruta más corta mediante el método Reaching . ^{[26] [27] [28]}

De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, ^[29] a saber

Problema 2. Encuentra la ruta de longitud total mínima entre dos nodos dados y . ${\displaystyle P}$ ${\displaystyle Q}$

Utilizamos el hecho de que, si es un nodo en la ruta mínima de a , el conocimiento de este último implica el conocimiento de la ruta mínima de a . ${\displaystyle R}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle R}$

es una paráfrasis del Principio de Optimalidad de Bellman en el contexto del problema del camino más corto.

Véase también

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

Notas

1. Controvertido, véase Moshe Sniedovich (2006). "El algoritmo de Dijkstra revisitado: la conexión de la programación dinámica". Control and Cybernetics . 35 : 599–620.y la parte de abajo.
2. Cormen y col. 2001
3. Fredman y Tarjan 1987
4. Richards, Hamilton. "Edsger Wybe Dijkstra". Premio AM Turing . Association for Computing Machinery . Consultado el 16 de octubre de 2017. En el Mathematical Centre, un proyecto importante era construir la computadora ARMAC. Para su inauguración oficial en 1956, Dijkstra ideó un programa para resolver un problema interesante para una audiencia no técnica: Dada una red de carreteras que conectan ciudades, ¿cuál es la ruta más corta entre dos ciudades designadas?
5. Frana, Phil (agosto de 2010). "Una entrevista con Edsger W. Dijkstra". Comunicaciones de la ACM . 53 (8): 41–47. doi :10.1145/1787234.1787249. S2CID  27009702.
6. Dijkstra, EW (1959). "Una nota sobre dos problemas relacionados con los grafos". Numerische Mathematik . 1 : 269–271. CiteSeerX 10.1.1.165.7577 . doi :10.1007/BF01386390. S2CID  123284777. 
7. Mehlhorn, Kurt ; Sanders, Peter (2008). "Capítulo 10. Caminos más cortos" (PDF) . Algoritmos y estructuras de datos: la caja de herramientas básica . Springer. doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
8. Schrijver, Alexander (2012). "Sobre la historia del problema del camino más corto" (PDF) . Documenta Mathematica . Documenta Mathematica Series: 155–167. doi :10.4171/dms/6/19. ISBN 978-3-936609-58-5.
9. Szcześniak, Ireneusz; Jajszczyk, Andrzej; Woźna-Szcześniak, Bożena (2019). "Dijkstra genérico para redes ópticas". Revista de Comunicaciones Ópticas y Redes . 11 (11): 568–577. arXiv : 1810.04481 . doi :10.1364/JOCN.11.000568. S2CID  52958911.
10. Szcześniak, Ireneusz; Woźna-Szcześniak, Bożena (2023), "Generic Dijkstra: Correctness and tractability", Simposio de gestión y operaciones de red IEEE/IFIP NOMS 2023-2023 , págs. 1 a 7, arXiv : 2204.13547 , doi : 10.1109/NOMS56928.2023.101543 22, ISBN 978-1-6654-7716-1, Número de identificación del sujeto  248427020
11. Felner, Ariel (2011). Documento de posición: Algoritmo de Dijkstra versus búsqueda de costo uniforme o un caso contra el algoritmo de Dijkstra. Proc. 4.° Simposio Internacional sobre Búsqueda Combinatoria. Archivado desde el original el 18 de febrero de 2020. Consultado el 12 de febrero de 2015 .En un problema de búsqueda de ruta, Felner descubre que la cola puede ser un factor 500-600 más pequeña, ocupando aproximadamente el 40% del tiempo de ejecución.
12. "ARMAC". Héroes anónimos de la historia de la informática holandesa . 2007. Archivado desde el original el 13 de noviembre de 2013.
13. Dijkstra, Edsger W., Reflexiones sobre "Una nota sobre dos problemas relacionados con los gráficos (PDF)"
14. Tarjan, Robert Endre (1983), Estructuras de datos y algoritmos de red , Serie de conferencias regionales CBMS_NSF en matemáticas aplicadas, vol. 44, Sociedad de matemáticas industriales y aplicadas, pág. 75, El tercer algoritmo clásico de árbol de expansión mínimo fue descubierto por Jarník y redescubierto por Prim y Dikstra; se lo conoce comúnmente como el algoritmo de Prim.
15. Prim, RC (1957). "Shortest connection networks and some generalizations" (PDF) . Bell System Technical Journal . 36 (6): 1389–1401. Bibcode :1957BSTJ...36.1389P. doi :10.1002/j.1538-7305.1957.tb01515.x. Archivado desde el original (PDF) el 18 de julio de 2017 . Consultado el 18 de julio de 2017 .
16. V. Jarník: O jistém problému minimálním [Sobre cierto problema mínimo ], Práce Moravské Přírodovědecké Společnosti, 6, 1930, págs. (en checo)
17. Gass, Saul; Fu, Michael (2013). "Algoritmo de Dijkstra". En Gass, Saul I; Fu, Michael C (eds.). Enciclopedia de investigación de operaciones y ciencia de la gestión . Vol. 1. Springer. doi : 10.1007/978-1-4419-1153-7 . ISBN . 978-1-4419-1137-7– vía Springer Link.
18. Fredman y Tarjan 1984.
19. Observe que p < dist[ u ] nunca puede cumplirse debido a la actualización dist[ v ] ← alt al actualizar la cola. Consulte https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key para obtener más información.
20. Chen, M.; Chowdhury, RA; Ramachandran, V.; Roche, DL; Tong, L. (2007). Colas de prioridad y algoritmo de Dijkstra – Informe técnico de UTCS TR-07-54 – 12 de octubre de 2007 (PDF) . Austin, Texas: Universidad de Texas en Austin, Departamento de Ciencias de la Computación.
21. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2022) [1990]. "22". Introducción a los algoritmos (4.ª ed.). MIT Press y McGraw-Hill. págs. 622–623. ISBN 0-262-04630-X.
22. Russell, Stuart ; Norvig, Peter (2009) [1995]. Inteligencia artificial: un enfoque moderno (3.ª ed.). Prentice Hall. págs. 75, 81. ISBN 978-0-13-604259-4.
23. A veces también búsqueda de menor costo primero : Nau, Dana S. (1983). "Sistemas informáticos expertos" (PDF) . Computer . 16 (2). IEEE: 63–85. doi :10.1109/mc.1983.1654302. S2CID  7301753.
24. Wagner, Dorothea; Willhalm, Thomas (2007). Técnicas de aceleración para cálculos de ruta más corta . STACS. págs. 23–36.
25. Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea (2010). "Combinación de técnicas de aceleración jerárquicas y dirigidas a objetivos para el algoritmo de Dijkstra". J. Experimental Algorithmics . 15 : 2.1. doi :10.1145/1671970.1671976. S2CID  1661292.
26. Sniedovich, M. (2006). "El algoritmo de Dijkstra revisitado: la conexión con la programación dinámica" (PDF) . Revista de Control y Cibernética . 35 (3): 599–620.Versión en línea del artículo con módulos computacionales interactivos.
27. Denardo, EV (2003). Programación dinámica: modelos y aplicaciones . Mineola, NY: Dover Publications . ISBN. 978-0-486-42810-9.
28. Sniedovich, M. (2010). Programación dinámica: fundamentos y principios . Francis & Taylor. ISBN 978-0-8247-4099-3.
29. Dijkstra 1959, pág. 270

Referencias

• 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 edición). MIT Press 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]". Comunicaciones de la ACM . 12 (11): 632–633. doi : 10.1145/363269.363610 . S2CID  6754003.
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes . 25.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación. IEEE . págs. 338–346. doi :10.1109/SFCS.1984.715934.
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes". Revista de la Asociación de Maquinaria Computacional . 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 modelo – Primer informe anual – 6 de junio de 1956 – 1 de julio de 1957 – Un estudio de técnicas modelo 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 de la ruta más corta" (PDF) . Revista de la 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 las rutas más cortas de una sola fuente". SIGACT News . 28 (2): 81–87. doi : 10.1145/261342.261352 . S2CID  18031586.
• Thorup, Mikkel (2000). "Sobre las 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.

Enlaces externos

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