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 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 de Dijkstra encuentra el camino más corto desde un nodo fuente determinado hasta 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, finalizando 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. Una aplicación común de los 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 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 el momento. Antes de que se descubrieran estructuras de colas de prioridad más avanzadas, el algoritmo original de Dijkstra se ejecutaba en el 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 utilizar una cola de prioridad 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. ${\displaystyle \Theta (|V|^{2})}$ ${\displaystyle |V|}$ ${\displaystyle \Theta (|E|+|V|\log |V|)}$

El algoritmo de Dijkstra se usa comúnmente en gráficos donde los pesos de los bordes son enteros positivos o números reales. Se puede generalizar a cualquier gráfico donde los pesos de los bordes estén parcialmente ordenados , siempre que las etiquetas posteriores (se produzca una etiqueta posterior al atravesar un borde) 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 costos uniformes y se formula como un ejemplo de la idea más general de búsqueda mejor primero . ^[11]

Historia

¿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 estás casi 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 cables necesarios 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 inicial (abajo a la izquierda, rojo) hasta un nodo objetivo (arriba a la derecha, verde) en un problema de planificación del movimiento de un robot . Los nodos abiertos representan el conjunto "provisional" (también conocido como conjunto de nodos "no visitados"). Los nodos rellenos son los visitados, y el color representa la distancia: cuanto más verde, más cerca. Los nodos en todas las direcciones diferentes se exploran de manera uniforme, apareciendo más o menos como un frente de onda circular , ya que el algoritmo de Dijkstra utiliza una heurística para elegir el camino más corto conocido 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. Marque todos los nodos como no visitados. Cree un conjunto de todos los nodos no visitados llamado conjunto no visitado .
2. Asigne a cada nodo una distancia desde el valor inicial: para el nodo inicial, es cero, y para todos los demás nodos, es infinito, ya que inicialmente no se conoce ninguna ruta para 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 inicial y N. ^[17]
3. Del conjunto no visitado, seleccione el nodo actual para que sea el que tenga la distancia finita más pequeña; Inicialmente, este será el nodo inicial, 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 preocupa la ruta a un nodo objetivo, podemos terminar aquí si el conjunto actual El nodo es el nodo objetivo. De lo contrario, podemos continuar buscando los caminos más cortos hacia todos los nodos accesibles.
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 actualmente asignada 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, luego actualícela a 8 (el camino de B a 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. Cuando hayamos terminado de considerar todos los vecinos no visitados del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado. Esto es para que un nodo visitado nunca se vuelva a verificar, lo cual es correcto porque la distancia registrada en el nodo actual es mínima (como se garantiza en el paso 3) y, por lo tanto, definitiva. Vuelva al paso 3.
6. Una vez que sale el bucle (pasos 3 a 5), ​​cada nodo visitado contendrá su distancia más corta desde el nodo inicial. Para obtener la ruta a un nodo visitado, comience con este nodo y seleccione repetidamente su vecino entrante con la distancia más corta, hasta llegar al nodo inicial.

Descripción

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 avanzando hacia 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.

Pseudocódigo

En el siguiente 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 de origen 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 , 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, conectan 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 proporciona 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 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 dist[u] mínima11 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 .

Usando una cola prioritaria

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 en apariencia, se menciona aquí, también en pseudocódigo:

1 función Dijkstra ( Gráfico , fuente ):2 crear cola de prioridad de vértice Q34 dist[ fuente ] ← 0 // Inicialización
5 Q .add_with_priority( fuente , 0) // la prioridad asociada es igual a dist[·]67 para cada vértice v en Graph.Vertices :8 si  v ≠ fuente
9 prev[ v ] ← UNDEFINED // Predecesor de v
10 dist[ v ] ← INFINITY // Distancia desconocida desde la fuente a v11 P.add_with_priority(v, INFINITO)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 anterior[ v ] ← u
20 dist[ v ] ← alt
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 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 procesando solo 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 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]

Prueba de corrección

Para demostrar la exactitud del algoritmo de Dijkstra, procedemos por inducción matemática del 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 sea la distancia más corta real para los nodos no visitados, mientras que sí lo es)[[dist[v]dist[u]dist[u]dist[v]

Caso base :

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

Paso inductivo :

Suponga que la hipótesis es válida para los nodos visitados. Deseamos mostrar que es válido 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 probar esta afirmación procedemos por contradicción. Si hubiera una ruta más corta, entonces esta ruta más corta contiene otro nodo no visitado o no.

• En el primer caso, sea w el primer nodo no visitado en este camino más corto. Según la hipótesis de inducción, los caminos más cortos 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 de la fuente a u a través de w tiene el costo de al menos + el costo mínimo de ir 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. Sin embargo, es como máximo porque, de lo contrario, la cola de prioridad habría elegido w 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 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 , 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 el origen hasta w utilizando solo los nodos visitados. Si hubiera una ruta más corta que no usara u , la habríamos encontrado previamente, y si hubiera una ruta más corta que usara 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. Por tanto, es la distancia más corta.dist[v]

Tiempo de ejecución

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. ${\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 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 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 . ${\displaystyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}$

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 ${\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|).}$

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} ${\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 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] [22] [23]} 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 * ⁄ ε ⌋} ) . ^[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 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". ^[24] Es posible que se necesiten combinaciones de tales técnicas para lograr un desempeño 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 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. ${\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 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.

Perspectiva de programación dinámica

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 . ^{[26] [27] [28]}

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

Problema 2. Encuentre el camino de longitud total mínima entre dos nodos dados y . ${\displaystyle P}$ ${\displaystyle Q}$

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 . ${\displaystyle R}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle R}$

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

Ver también

• Un* algoritmo de búsqueda
• 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, ver Moshe Sniedovich (2006). "Revisión del algoritmo de Dijkstra: la conexión de programación dinámica". Control y Cibernética . 35 : 599–620.y debajo de la parte.
2. Cormen et al. 2001
3. Fredman y Tarjan 1987
4. Richards, Hamilton. "Edsger Wybe Dijkstra". Premio AM Turing . Asociación para Maquinaria de Computación . Consultado el 16 de octubre de 2017 . 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?
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 en relación con los gráficos". Matemática numérica . 1 : 269–271. CiteSeerX 10.1.1.165.7577 . doi :10.1007/BF01386390. S2CID  123284777. 
7. Mehlhorn, Kurt ; Lijadoras, Peter (2008). "Capítulo 10. Caminos más cortos" (PDF) . Algoritmos y estructuras de datos: la caja de herramientas básica . Saltador. doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
8. Schrijver, Alejandro (2012). "Sobre la historia del problema del camino más corto" (PDF) . Documenta Matemática . Serie Documenta Mathematica: 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, S2CID  248427020
11. Felner, Ariel (2011). Documento de posición: algoritmo de Dijkstra versus búsqueda de costos uniformes o un caso contra el algoritmo de Dijkstra. Proc. 4to 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 rutas, Felner descubre que la cola puede ser entre 500 y 600 veces menor, ocupando alrededor del 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 sobre 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ínima fue descubierto por Jarník y redescubierto por Prim y Dikstra; se le conoce comúnmente como algoritmo de Prim.
15. Prim, RC (1957). «Redes de conexión más cortas y algunas generalizaciones» (PDF) . Revista técnica del sistema Bell . 36 (6): 1389-1401. Código bibliográfico : 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, Saúl; Fu, Michael (2013). "Algoritmo de Dijkstra". En Gass, Saúl I; Fu, Michael C (eds.). Enciclopedia de investigación de operaciones y ciencias de la gestión . vol. 1. Saltador. doi : 10.1007/978-1-4419-1153-7 . ISBN 978-1-4419-1137-7– vía Enlace Springer.
18. Fredman y Tarjan 1984.
19. Observe que p < dist[ u ] nunca puede mantenerse 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 prioritarias y algoritmo de Dijkstra - Informe técnico 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, Estuardo ; 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) . Computadora . 16 (2). IEEE: 63–85. doi :10.1109/mc.1983.1654302. S2CID  7301753.
24. Wagner, Dorotea; Willhalm, Thomas (2007). "Técnicas de aceleración para cálculos del camino más corto" . STAC. págs. 23–36.
25. Bauer, Reinhard; Delling, Daniel; Lijadoras, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorotea (2010). "Combinando técnicas de aceleración jerárquicas y dirigidas a objetivos para el algoritmo de Dijkstra". J. Algorítmica experimental . 15 : 2.1. doi :10.1145/1671970.1671976. S2CID  1661292.
26. Sniedovich, M. (2006). "Revisión del algoritmo de Dijkstra: la conexión de 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, Nueva York: Publicaciones de Dover . ISBN 978-0-486-42810-9.
28. Sniedovich, M. (2010). Programación dinámica: fundamentos y principios . Francisco y Taylor. ISBN 978-0-8247-4099-3.
29. Dijkstra 1959, pag. 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 ed.). Prensa del MIT y McGraw-Hill . págs. 595–601. ISBN 0-262-03293-7.
• Marcar, Robert B. (1969). "Algoritmo 360: bosque de camino más corto 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 Informática. 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 de Computación . 34 (3): 596–615. doi : 10.1145/28869.28874 . S2CID  7904683.
• Zhan, F. Benjamín; Mediodía, Charles E. (febrero de 1998). "Algoritmos de ruta más corta: una evaluación utilizando redes de carreteras reales". Ciencia del transporte . 32 (1): 65–73. doi :10.1287/trsc.32.1.65. S2CID  14986297.
• Leyzorek, M.; Gris, 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 - Estudio de técnicas modelo para sistemas de comunicación . Cleveland, Ohio: Instituto de Tecnología Case.
• Knuth, DE (1977). "Una generalización del algoritmo de Dijkstra". Cartas de procesamiento de información . 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) . 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 los caminos más cortos de una sola fuente". Noticias SIGACT . 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). "Rutas más cortas no dirigidas de una sola fuente con pesos enteros positivos en tiempo lineal". Revista de la 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 usando TDD, Robert Cecil Martin , The Clean Code Blog