Algoritmo de Dijkstra

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

algoritmo de búsqueda de Gráficos

Algoritmo de Dijkstra (DYKE-strəz) es un algoritmo para encontrar las rutas más cortas entre nodos en un gráfico, 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.

El algoritmo existe en muchas variantes. El algoritmo original de Dijkstra encontró la ruta más corta entre dos nodos dados, pero una variante más común fija un solo nodo como el "origen" y encuentra las rutas más cortas desde el origen hasta todos los demás nodos del gráfico, produciendo un árbol de rutas más cortas.

Para un nodo de origen dado en el gráfico, el algoritmo encuentra la ruta más corta entre ese nodo y todos los demás. También se puede usar para encontrar las rutas más cortas desde un solo nodo a un solo nodo de destino deteniendo el algoritmo una vez que se haya determinado la ruta más corta al nodo de destino. Por ejemplo, si los nodos del gráfico representan ciudades y los costes de los caminos 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 con peaje y otros obstáculos), entonces Dijkstra&#39 El algoritmo de;s se puede utilizar para encontrar la ruta más corta entre una ciudad y todas las demás ciudades. Una aplicación ampliamente utilizada de los algoritmos de ruta más corta son los protocolos de enrutamiento de red, más notablemente 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 enteros positivos o números reales, que están totalmente ordenados. Se puede generalizar para usar cualquier etiqueta que esté parcialmente ordenada, siempre que las etiquetas subsiguientes (se produce una etiqueta subsiguiente cuando se atraviesa un borde) sean monótonamente no decrecientes. Esta generalización se denomina algoritmo genérico de ruta más corta de Dijkstra.

El algoritmo de Dijkstra utiliza una estructura de datos para almacenar y buscar soluciones parciales ordenadas por distancia desde el principio. Mientras el algoritmo original utiliza una cola de min-prioridad y funciona en el tiempo ${displaystyle Theta ((|V|+|E|)log |V|)}$ (donde) $|V|$ es el número de nodos y $|E|$ es el número de bordes), también se puede implementar en ${displaystyle Theta (|V|^{2})}$ usando un array. La idea de este algoritmo también se da en Leyzorek et al. 1957. Fredman & Tarjan 1984 propone utilizar una cola de min-prioridad de Fibonacci para optimizar la complejidad del tiempo de funcionamiento ${displaystyle Theta (|E|+|V|log |V|)}$ . Este es asintomáticamente el algoritmo más rápido conocido de código único más rápido para gráficos arbitrarios dirigidos con pesos no negativos sin límites. Sin embargo, los casos especializados (como pesos ligados o enteros, gráficos acíclicos dirigidos, etc.) pueden mejorarse aún más según se detalla en variantes especializadas. Además, si se permite el preprocesamiento de algoritmos como las jerarquías de contracción pueden ser hasta siete órdenes de magnitud más rápido.

En algunos campos, la inteligencia artificial en particular, 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 la búsqueda del mejor primero.

Historia

¿Cuál es la manera más corta de viajar desde Rotterdam a Groningen, en general: de ciudad dada a ciudad dada. Es el algoritmo para el camino más corto, que diseñé en unos veinte minutos. Una mañana estaba de compras en Amsterdam con mi joven novia, y cansado, nos sentamos en la terraza de la cafetería para tomar una taza de café y estaba pensando en si podía hacer esto, y entonces diseñé el algoritmo para el camino más corto. Como dije, fue una invención de veinte minutos. De hecho, fue publicado en el 59, tres años después. La publicación sigue siendo legible, es, de hecho, bastante agradable. Una de las razones por las que es tan agradable fue que lo diseñé sin lápiz y papel. Aprendí más tarde que una de las ventajas de diseñar sin lápiz y papel es que casi estás obligado a evitar todas las complejidades evitables. Eventualmente, ese algoritmo se convirtió en mi gran asombro, una de las piedras angulares de mi fama.
—Edsger Dijkstra, en entrevista con Philip L. Frana, Comunicaciones de la ACM, 2001

Dijkstra pensó en el problema del camino más corto cuando trabajaba en el Centro Matemático de Ámsterdam en 1956 como programador para demostrar las capacidades de una nueva computadora llamada ARMAC. Su objetivo era elegir tanto un problema como una solución (que sería producida por computadora) que las personas que no saben de computación 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, por lo que 6 bits serían suficientes para codificar el número de ciudad). Un año más tarde, 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). Dijkstra publicó el algoritmo en 1959, dos años después de Prim y 29 años después de Jarník.

Algoritmo

Ilustración del algoritmo de Dijkstra encontrando un camino desde un nodo de inicio (abajo izquierdo, rojo) a un nodo de gol (abajo derecho, verde) en un problema de planificación de movimiento robot. Los nodos abiertos representan el conjunto "tentante" (también conjunto de nodos "no previstos"). Nodos llenos son los visitados, con el color que representa la distancia: el más verde, el más cercano. Los nodos en todas las direcciones se exploran uniformemente, apareciendo más o menos como una onda circular, ya que el algoritmo de Dijkstra utiliza una heurística idénticamente igual a 0.

Dejemos que el nodo en el que estamos comenzando se llame nodo inicial. Sea la distancia del nodo Y la distancia del nodo inicial a Y. El algoritmo de Dijkstra comenzará inicialmente con distancias infinitas e intentará mejorarlas paso a paso.

Marca todos los nodos sin mirar. Crear un conjunto de todos los nodos no vistos llamados los conjunto no previsto.
Asignar a cada nodo a Distancia provisional valor: establecerlo a cero para nuestro nodo inicial y para infinito para todos los demás nodos. Durante el funcionamiento del algoritmo, la distancia tentativa de un nodo v es la longitud del camino más corto descubierto hasta ahora entre el nodo v y el Empieza Nodo. Puesto que inicialmente ningún camino es conocido por cualquier otro vértice que la fuente misma (que es un camino de la longitud cero), todas las otras distancias tentativas se fijan inicialmente para el infinito. Establecer el nodo inicial como corriente.
Para el nodo actual, considere a todos sus vecinos no vistos y calcula sus distancias tentativas a través del nodo actual. Compare la distancia tentativa recién calculada a la que se asigna actualmente al vecino y la asigne 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 un vecino B tiene longitud 2, entonces la distancia a B a través de A será 6 + 2 = 8. Si B fue marcado previamente con una distancia mayor a 8 entonces cambiar a 8. De lo contrario, se mantendrá el valor actual.
Cuando terminemos de considerar a todos los vecinos no vistos del nodo actual, marque el nodo actual como visitado y retírelo del conjunto no visto. Un nodo visitado nunca será revisado de nuevo (esto es válido y óptimo en relación con el comportamiento en el paso 6.: que los próximos nodos a visitar siempre estarán en el orden de 'la distancia más reducida de nodo inicial primero' así que cualquier visita después tendría una mayor distancia).
Si el nodo de destino se ha marcado visitado (cuando se planea una ruta entre dos nodos específicos) o si la distancia más pequeña entre los nodos en el conjunto no previsto es infinidad (cuando se planea una traversal completa; se produce cuando no hay conexión entre el nodo inicial y los nodos no visibles), entonces parar. El algoritmo ha terminado.
De lo contrario, seleccione el nodo no visto que está marcado con la distancia más pequeña tentativa, fijarlo como el nuevo actual nodo, y volver al paso 3.

Al planificar una ruta, en realidad no es necesario esperar hasta que el nodo de destino sea "visitado" como arriba: el algoritmo puede detenerse una vez que el nodo de destino tenga la distancia tentativa más pequeña entre todos los "no visitados" nodos (y por lo tanto podría ser seleccionado como el próximo 'actual').

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 inicio) a cualquier otra intersección en el mapa con infinito. Esto no se hace para dar a entender que hay una distancia infinita, sino para señalar que esas intersecciones aún no se han visitado. Algunas variantes de este método dejan las intersecciones' distancias 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 inicio y la distancia hasta él (la etiqueta de la intersección) será cero. Para iteraciones subsiguientes (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é 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 la intersección no visitada. 39;s valor actual. 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 previamente conocidos. Para facilitar la identificación de la ruta más corta, 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. Una vez que haya 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 inicio), 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 él y no se volverán a visitar ni a ellas.

Continúe este proceso de actualizar las intersecciones vecinas con las distancias más cortas, marque la intersección actual como visitada y muévase 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 de cualquier intersección visitada), habrá determinado el camino más corto desde el punto de partida y podrá trazar el 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 alcanzado el nodo de destino) siguiendo las instrucciones de los nodos. padres 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 una "exploración" hacia el destino como cabría esperar. Más bien, la única consideración para determinar el siguiente "actual" intersección 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, es claro cómo el algoritmo encuentra necesariamente 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 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 el origen hasta el 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 (equivalentemente, es el siguiente salto en el camino 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 la menor dist[u] valor. Graph.Edges(u, v) devuelve la longitud del borde que une (es decir, la distancia entre) los dos vecinos -nodos u y v. La variable alt en la línea 14 es la longitud de la ruta desde el nodo raíz hasta el nodo vecino v si pasara por u. Si esta ruta es más corta que la ruta actual más corta registrada para v, esa ruta actual se reemplaza con esta altruta.

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

 1 función Dijkstra(Gráfico, fuente):
2
3 para cada uno vertex v dentro Gráfico.Vertices:
4 dist[v← INFINITY
5 prev[v← UNDEFINED
6 añadir v a Q7 dist[fuente← 0
8
9 mientras Q no está vacío:
10 u ← vértice en Q con min dist[u]
11 eliminar u de Q12
13 para cada uno vecino v de u todavía Q:
14 Alt ← dist[u] + Gráfico.Edges(u, v)
15 si Alt - No.v]:
16 dist[v← Alt17 prev[v← u18
19 retorno dist[], prev[]

Si solo estamos interesados en un camino más corto entre los vértices source y target, podemos terminar la búsqueda después de la línea 10 si u = target. Ahora podemos leer la ruta más corta desde source a target por iteración inversa:

1 S ← secuencia vacía
2 u ← objetivo3 si prev[u] se define o u = fuente: // Hacer algo sólo si el vértice es accesible4 mientras u se define: // Construir el camino más corto con una pila S5 inserción u al principio S // Empuja el vértice sobre la pila6 u ← prev[u] // Desvío del objetivo a la fuente

Ahora la secuencia S es la lista de vértices que constituyen uno de los caminos más cortos desde source a target, o la secuencia vacía si no existe una ruta.

Un problema más general sería encontrar todas las rutas más cortas entre source y target (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 satisfagan la condición de relajación. Por ejemplo, si tanto r como source se conectan a target y ambos se encuentran en diferentes caminos más cortos a través de target (porque el costo de borde es el mismo en ambos casos), entonces agregaríamos r y source a prev[objetivo]. Cuando se complete el algoritmo, la estructura de datos prev[] 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 inicial, 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 realmente 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 de prioridad

Una cola de prioridad mínima es un tipo de datos abstracto que proporciona 3 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 conducir a tiempos de cálculo más rápidos que el uso de una cola básica. En particular, el montón de Fibonacci o la cola de Brodal ofrecen implementaciones óptimas para esas 3 operaciones. Como el algoritmo es ligeramente diferente, lo mencionamos aquí, también en pseudocódigo:

1 función Dijkstra(Gráfico, fuente):
2 dist[2]fuente← 0 // Iniciación3
4 crear la cola de prioridad del vértice Q
5
6 para cada uno vertex v dentro Gráfico.Vertices:
7 si v ل fuente8 dist[v← INFINITY // Distancia desconocida de la fuente a v9 prev[v← UNDEFINED // Predecesador de v10
11 Q.add_with_priority(v, dist[v])
12
13
14 mientras Q no está vacío: // El bucle principal15 u ← Q.extract_min() // Quitar y devolver el mejor vértice16 para cada uno vecino v de u: // Ir a través de todos v vecinos de u17 Alt ← dist[u] + Gráfico.Edges(u, v)
18 si Alt - No.v]:
19 dist[v← Alt20 prev[v← u21 Q.decrease_priority(v, Alt)
22
23 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 fuente; luego, dentro del if alt < dist[v], el decrease_priority() se convierte en un add_with_priority() operación si el nodo no está ya en la cola.

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 se está volviendo a visitar o que aún no se encontró una conexión más corta. Esto se puede hacer extrayendo adicionalmente la prioridad asociada p de la cola y procesando únicamente if p == dist[u] dentro del bucle while Q no está vacío.

Estas alternativas pueden usar colas de prioridad completamente basadas en arreglos sin funcionalidad de reducción de clave, que se ha descubierto que logran tiempos de cómputo aún más rápidos en la práctica. Sin embargo, se encontró que la diferencia en el rendimiento era más estrecha para los gráficos más densos.

Prueba de corrección

La prueba del algoritmo de Dijkstra se construye por inducción sobre el número de nodos visitados.

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

El caso base es cuando solo hay un nodo visitado, a saber, el nodo inicial fuente, en cuyo caso la hipótesis es trivial.

Luego, asuma la hipótesis para k-1 nodos visitados. A continuación, elegimos u para que sea el siguiente nodo visitado según el algoritmo. Afirmamos que dist[u] es la distancia más corta desde source hasta 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, ya sea que la ruta más corta contenga otro nodo no visitado o no.

En el primer caso, sea w el primer nodo no visitado en la ruta más corta. Según la hipótesis de inducción, el camino más corto desde fuente hasta u y w a través del nodo visitado solo ha costado dist[u] y dist[w] respectivamente. Eso significa que el costo de pasar de fuente a u a través de w tiene el costo de al menos dist[w] + el costo mínimo de pasar de w a u . Como los costos de borde son positivos, el costo mínimo de pasar de w a u es un número positivo.

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] pero dist[w] + un número positivo < dist[u].

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

Para todos los demás nodos visitados v, la hipótesis de inducción nos dijo que dist[v] es la distancia más corta desde source ya, y el paso del algoritmo no cambia eso.

Después de procesar u seguirá siendo cierto que para cada nodo no visitado w, dist[w] será la distancia más corta desde source a w usando solo nodos visitados, porque si hubiera un camino más corto que no pasa por u lo habríamos encontrado previamente, y si hubiera un camino más corto usando u lo habríamos actualizado al procesar u.

Después de visitar todos los nodos, la ruta más corta desde fuente a cualquier nodo v consta solo de nodos visitados, por lo tanto dist[v] es la distancia más corta.

Tiempo de ejecución

Libras del tiempo de funcionamiento del algoritmo de Dijkstra en un gráfico con bordes $E$ y vértices $V$ se puede expresar como una función del número de bordes, denotados $|E|$ , y el número de vértices, denotados $|V|$ , usando notación grande. La complejidad vinculada depende principalmente de la estructura de datos utilizada para representar el conjunto $Q$ . En los siguientes puntos superiores se pueden simplificar porque $|E|$ es $O(|V|^{2})$ para cualquier gráfico, pero esa simplificación ignora el hecho de que en algunos problemas, otros límites superiores en $|E|$ Puede esperar.

Para cualquier estructura de datos para el conjunto de vértices $Q$ , el tiempo de ejecución es de

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

Donde $T_{mathrm {dk} }$ y $T_{mathrm {em} }$ son las complejidades de las disminucion-key y extracto-minimo operaciones 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 vinculada, y bordes como una lista de adjacency o matriz. En este caso, el extracto-minimo es simplemente una búsqueda lineal a través de todos los vértices en $Q$ , así que el tiempo de funcionamiento es ${displaystyle Theta (|E|+|V|^{2})=Theta (|V|^{2})}$ .

Para gráficos escasos, es decir, gráficos con mucho menos que $|V|^{2}$ bordes, el algoritmo de Dijkstra puede ser implementado más eficientemente mediante el almacenamiento del gráfico en forma de listas de adyacency y el uso de un árbol de búsqueda binaria auto-balanceante, montón binario, montón de emparejamiento, o el montón de Fibonacci como una cola prioritaria para implementar la extracción mínima eficiente. Para realizar los pasos de baja clave en un montón binario eficientemente, es necesario utilizar una estructura auxiliar de datos que mapea cada vértice a su posición en el montón, y mantener esta estructura hasta la fecha como la cola prioritaria $Q$ cambios. Con un árbol de búsqueda binaria auto-balancing o un montón binario, el algoritmo requiere

Theta ((|E|+|V|)log |V|)

tiempo en el peor de los casos (donde $log$ denota el logaritmo binario $log _{2}$ ); para gráficos conectados este tiempo límite puede ser simplificado a $Theta (|E|log |V|)$ . El montón de Fibonacci mejora esto a

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

Cuando se utilizan montones binarios, la complejidad promedio del tiempo de caso es menor que la peor: asumiendo que los costos de borde se extraen independientemente de una distribución de probabilidad común, el número esperado de disminucion-key operaciones sujetas a ${displaystyle Theta (|V|log(|E|/|V|))}$ , dando un tiempo de funcionamiento total

{displaystyle Oleft(|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 contiene solo un elemento e insertar nuevos elementos a medida que se descubren (en lugar de hacer una clave decreciente, verifique si la clave está en la cola; si es decir, disminuya su clave, de lo contrario insértela). Esta variante tiene los mismos límites en el peor de los casos que la variante común, pero en la práctica mantiene una cola de prioridad más pequeña, lo que acelera las operaciones de la cola.

Además, al no insertar todos los nodos en un gráfico, es 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 de destino en gráficos infinitos o demasiado grandes para representarlos en la memoria. El algoritmo resultante se llama búsqueda de costo uniforme (UCS) en la literatura de inteligencia artificial y se puede expresar en pseudocódigo como

procedimiento uniform_cost_search(start) esnodo ← empezar
frontera ← cola prioritaria que contiene nodo solamente
← juego vacío
 do si La frontera está vacía entonces retorno fracaso
nodo ← frontera.pop()
 si nodo es un estado objetivo entonces retorno solución (nodo)
expandido.add(nodo)
 para cada uno de los vecinos de nodo n do si n no está en expansión y no en frontera entoncesborder.add(n)
 si n está en frontera con mayor costo
sustituir el nodo existente por n

La complejidad de este algoritmo se puede expresar de forma alternativa para gráficos muy grandes: cuando $C *$ es la longitud de la ruta más corta desde el nodo inicial hasta cualquier nodo que satisfaga el "objetivo" predicado, cada borde ha costado al menos $ε$ , y la cantidad de vecinos por nodo está limitada por $b$ , entonces la complejidad temporal y espacial del peor de los casos del algoritmo está en $O (b 1+⌊ C * ⁄ ε ⌋)$ .

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 forman el segmento medio de las rutas más cortas (enrutamiento basado en alcance) y descomposiciones jerárquicas del gráfico de entrada que reducen $s - t$ enrutamiento para conectar $s$ y $t$ a 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'. Pueden ser necesarias combinaciones de tales técnicas para un rendimiento práctico óptimo en problemas específicos.

Variantes especializadas

Cuando los pesos del arco son pequeños números enteros (limitados por un parámetro $C$ ), colas especializadas que aprovechan este hecho se pueden utilizar 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 entero positivos, que utiliza una cola de cubo para obtener un tiempo de funcionamiento ${displaystyle O(|E|+|V|C)}$ . El uso de un árbol Van Emde Boas como la cola prioritaria trae la complejidad a ${displaystyle O(|E|log log C)}$ (Ahuja y otros 1990). Otra variante interesante basada en una combinación de un nuevo montón de ráx y el conocido montón de Fibonacci corre en el tiempo ${displaystyle O(|E|+|V|{sqrt {log C}})}$ (Ahuja y otros 1990). Finalmente, los mejores algoritmos en este caso especial son los siguientes. El algoritmo dado por (Thorup 2000) se ejecuta en $O(|E|log log |V|)$ tiempo y el algoritmo dado por (Raman 1997) ${displaystyle O(|E|+|V|min{(log |V|)^{1/3+varepsilon },(log C)^{1/4+varepsilon }})}$ tiempo.

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 óptimas desde el punto de vista matemático. Para obtener una lista clasificada de soluciones menos que óptimas, primero se calcula la solución óptima. Un solo borde que aparece en la solución óptima se elimina del gráfico 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 un nuevo camino más corto. Luego, las soluciones secundarias se clasifican y 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 usar en gráficos con pesos de borde negativos, siempre que el gráfico no contenga un ciclo negativo al que se pueda acceder 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 declaración asume 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 manejar bordes 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 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 en el algoritmo de Dijkstra es similar al proceso codicioso que se usa en el algoritmo de Prim. El propósito de Prim es encontrar un árbol de expansión mínimo que conecte todos los nodos en el gráfico; Dijkstra se ocupa de sólo dos nodos. Prim's no evalúa el peso total de la ruta desde el nodo inicial, solo los bordes individuales.

La búsqueda en amplitud se puede ver 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 la programación dinámica para el problema del camino más corto mediante el método Reaching.

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

Problema 2. Encontrar el camino de la longitud total mínima entre dos nodos dados $P$ y $Q$ .
Usamos el hecho de que, si $R$ es un nodo en el camino mínimo desde $P$ a $Q$ , el conocimiento de este último implica el conocimiento del camino mínimo desde $P$ a $R$ .

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

Aplicaciones

Las rutas de menor costo se calculan, por ejemplo, para establecer pistas de líneas eléctricas o oleoductos. El algoritmo también se ha utilizado para calcular senderos óptimos de larga distancia en Etiopía y contrastarlos con la situación sobre el terreno.

Contenido relacionado

Más resultados...