LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

No debe confundirse con el algoritmo de proyección de Dykstra .

Algoritmo de Dijkstra

El algoritmo de Dijkstra para encontrar el camino más corto entre una y b . Selecciona el vértice no visitado con la distancia más baja, calcula la distancia que atraviesa a cada vecino no visitado y actualiza la distancia del vecino si es más pequeña. Mark visitó (se puso en rojo) cuando se hizo con los vecinos.
Clase	Algoritmo de búsqueda
Estructura de datos	Grafico
Peor desempeño	$${\ displaystyle O (| E | + | V | \ log | V |)}

Gráficos yalgoritmos de búsqueda de árboles.
α – β UNA* SEGUNDO* Retroceso Haz Bellman – Ford Mejor primero Bidireccional Borůvka Rama y atado BFS Museo Británico RE* DFS Dijkstra Edmonds Floyd – Warshall Búsqueda de flecos Montañismo IDA * Profundización iterativa Johnson Punto de salto Kruskal BFS lexicográfico LPA * Remilgado SMA * SPFA
Listados
Algoritmos de grafos Algoritmos de búsqueda Lista de algoritmos de grafos
Temas relacionados
Programación dinámica Traversal de grafos Travesía de árboles Buscar juegos
v t mi

El algoritmo de Dijkstra (o ruta más corta de Dijkstra primer algoritmo , algoritmo SPF ) ^[1] es un algoritmo para la búsqueda de las rutas más cortas entre los nodos en un gráfico, 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. ^{[2] [3] [4]}

El algoritmo existe en muchas variantes; La variante original de Dijkstra encontró la ruta más corta entre dos nodos, ^[4] pero una variante más común corrige un solo nodo como el nodo "fuente" y encuentra las rutas más cortas desde la fuente a todos los demás nodos en el gráfico, produciendo un árbol de ruta más corta .

Para un nodo fuente dado en el gráfico, el algoritmo encuentra la ruta más corta entre ese nodo y todos los demás. ^{[5] : 196–206}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 ha determinado la ruta más corta al nodo de destino. Por ejemplo, si los nodos del gráfico representan ciudades y los costos de la trayectoria de borde representan distancias de conducción entre pares de ciudades conectadas por una carretera directa (por simplicidad, ignore las luces rojas, las señales de alto, las carreteras de peaje y otras obstrucciones), se puede usar el algoritmo de Dijkstra para encontrar la ruta más corta entre una ciudad y todas las demás ciudades. Una aplicación ampliamente utilizada del algoritmo de ruta más corta son los protocolos de enrutamiento de red , especialmente IS-IS.(Sistema intermedio a sistema intermedio) y Abrir primero la ruta más corta ( OSPF ). También se emplea como subrutina en otros algoritmos como el de Johnson .

El algoritmo de Dijkstra usa etiquetas que son números enteros positivos o números reales, que tienen el estricto ordenamiento débil definido. De manera interesante, Dijkstra puede generalizarse para usar etiquetas definidas de cualquier manera, siempre que tengan el orden parcial estricto definido, y siempre que las etiquetas subsiguientes (una etiqueta subsiguiente se produzca al atravesar un borde) sean monótonamente no decrecientes. Esta generalización se denomina algoritmo de ruta más corta de Dijkstra ^[6] .

El algoritmo original de Dijkstra no usa una cola de prioridad mínima y se ejecuta en el tiempo $${\ displaystyle O (| V | ^ {2})} (dónde $${\ displaystyle | V |}es el numero de nodos). La idea de este algoritmo también se da en Leyzorek et al. 1957 . La implementación basada en una cola de prioridad mínima implementada por un montón Fibonacci y ejecutándose en$${\ displaystyle O (| E | + | V | \ log | V |)} (dónde $${\ displaystyle | E |}es el número de bordes) se debe a Fredman y Tarjan 1984 . Este es asintóticamente el algoritmo de ruta más corto conocido de fuente única más rápido para gráficos dirigidosarbitrarios con ponderaciones no negativas ilimitadas. Sin embargo, los casos especializados (como los pesos acotados / enteros, los gráficos acíclicos dirigidos, etc.) pueden mejorarse aún más como se detalla en § Variantes especializadas .

En algunos campos, la inteligencia artificial en particular, el algoritmo de Dijkstra o una variante de él se conoce como búsqueda de costo uniforme y se formula como un ejemplo de la idea más general de búsqueda de primer nivel .

Historia [ editar ]

¿Cuál es la forma más corta de viajar de Rotterdam a Groningen , en general: de una ciudad determinada a otra? Es el algoritmo para el camino más corto , que diseñé en unos veinte minutos. Una mañana estaba de compras en Amsterdamcon mi joven prometida, y cansada, nos sentamos en la terraza del café a tomar una taza de café y pensé en si podría hacerlo, y luego 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 todavía es legible, es, de hecho, bastante agradable. Una de las razones por las que es tan agradable fue que lo diseñé sin lápiz ni papel. Más tarde supe que una de las ventajas de diseñar sin lápiz y papel es que casi te ves obligado a evitar todas las complejidades evitables. Con el tiempo, ese algoritmo se convirtió, para mi asombro, en una de las piedras angulares de mi fama.

-  Edsger Dijkstra, en una entrevista con Philip L. Frana, Comunicaciones de la ACM, 2001 ^[3]

Dijkstra pensó en el problema de la ruta más corta cuando trabajaba en el Centro de Matemáticas en Amsterdamen 1956 como programador para demostrar las capacidades de una nueva computadora llamada ARMAC. ^[8] 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 de ruta 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 ciudad). ^[3]Un año más tarde, se encontró con otro problema de los ingenieros de hardware que trabajan 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, volvió a descubrir el algoritmo conocido como algoritmo de árbol de expansión mínima de Prim (conocido anteriormente por Jarník , y también redescubierto por Prim ). ^[9] [10] Dijkstra publicó el algoritmo en 1959, dos años después de Prim y 29 años después de Jarník. ^[11] [12]

Algoritmo [ editar ]

Ilustración del algoritmo de Dijkstra que encuentra una ruta desde un nodo de inicio (abajo a la izquierda, rojo) a un nodo de objetivo (arriba a la derecha, verde) en un problema de planificación de movimiento de robot . Los nodos abiertos representan el conjunto "tentativo" (también conocido como conjunto de nodos "no visitados"). Los nodos rellenos son los visitados, con el color que representa la distancia: cuanto más verde, más cerca. Los nodos en todas las diferentes direcciones se exploran de manera uniforme, apareciendo más o menos como un frente de ondacircular, ya que el algoritmo de Dijkstra utiliza una heurística idéntica a 0.

Deje que el nodo en el que estamos empezando se llame nodo inicial . Deje que la distancia de nodo Y sea la distancia desde el nodo inicial a Y . El algoritmo de Dijkstra asignará algunos valores de distancia iniciales e intentará mejorarlos paso a paso.

1. Marcar todos los nodos no visitados. Cree un conjunto de todos los nodos no visitados denominado conjunto no visitado .
2. Asigne a cada nodo un valor de distancia tentativa: establézcalo en cero para nuestro nodo inicial e infinito para todos los demás nodos. Establecer el nodo inicial como actual. ^[13]
3. Para el nodo actual, considere a todos sus vecinos no visitados y calcule sus distancias tentativas a través del nodo actual. Compare la distancia tentativa recién calculada con el valor asignado actual y asigne el menor. Por ejemplo, si el nodo A actual está marcado con una distancia de 6, y el borde que lo conecta con un vecino B tiene una longitud 2, entonces la distancia de B a A será 6 + 2 = 8. Si B estaba marcado previamente con una distancia mayor que 8 luego cámbiela a 8. De lo contrario, mantenga el valor actual.
4. Cuando hayamos terminado de considerar a todos los vecinos no visitados del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado . Un nodo visitado nunca será verificado de nuevo.
5. Si el nodo de destino se ha marcado como visitado (al planificar una ruta entre dos nodos específicos) o si la distancia tentativa más pequeña entre los nodos en el conjunto no visitado es infinita (cuando se planifica un recorrido completo; ocurre cuando no hay conexión entre el nodo inicial y restantes nodos no visitados), luego se detienen. El algoritmo ha terminado.
6. De lo contrario, seleccione el nodo no visitado que está marcado con la distancia tentativa más pequeña, configúrelo como el nuevo "nodo actual" y vuelva al paso 3.

Cuando se planifica una ruta, en realidad no es necesario esperar hasta que el nodo de destino se "visite" como antes: el algoritmo puede detenerse una vez que el nodo de destino tenga la distancia tentativa más pequeña entre todos los nodos "no visitados" (y por lo tanto podría seleccionarse como siguiente "actual").

Descripción [ editar ]

Nota: para facilitar la comprensión, esta discusión utiliza los términos intersección , camino y mapa ; sin embargo, en terminología formal, estos términos son vértice , borde y gráfico , respectivamente.

Suponga que le gustaría encontrar la ruta más corta entre dos intersecciones en un mapa de la ciudad: un punto de partida y un destino . El algoritmo de Dijkstra marca inicialmente la distancia (desde el punto de inicio) a todas las demás intersecciones del mapa con infinito . Esto se hace para no implicar que hay una distancia infinita, sino para observar que esas intersecciones aún no se han visitado. Algunas variantes de este método dejan las distancias de las intersecciones sin marcar . 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 a ella (la etiqueta de la intersección) serácero . Para las iteraciones posteriores (después de la primera), la intersección actual será una intersección no visitada más cercana al punto de inicio (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 vuelve 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 la ruta a través de la intersección actual es más corta que las rutas conocidas anteriormente. Para facilitar la identificación de la ruta más corta, marque con lápiz el camino con una flecha que apunte a la intersección de la nueva etiqueta si lo etiqueta / vuelve a etiquetar, y borre todos los demás que la apuntan. Después de haber actualizado las distancias a cadaintersección vecina , marque la intersección actual como visitada y seleccione una intersección no visitada con una distancia mínima (desde el punto inicial), o la etiqueta más baja, como la intersección actual. Las intersecciones marcadas como visitadas se etiquetan con la ruta más corta desde el punto de inicio hasta ellas y no se volverán a visitar ni a ellas.

Continúe este proceso de actualización de las intersecciones vecinas con las distancias más cortas, marque la intersección actual como visitada y continúe con 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), ha determinado el camino más corto desde el punto de partida y puede seguir su camino siguiendo las flechas en sentido inverso . En las implementaciones del algoritmo, esto suele hacerse (después de que el algoritmo haya alcanzado el nodo de destino) siguiendo a los padres de los nodos desde el nodo de destino hasta el nodo de inicio; por eso también hacemos un seguimiento de los padres de cada nodo.

Este algoritmo no hace ningún intento de "exploración" directa hacia el destino como se podría esperar. Más bien, la única consideración al determinar la próxima intersección "actual" es su distancia desde el punto de inicio. Por lo tanto, este algoritmo se expande hacia afuera desde el punto de inicio, considerando interactivamente cada nodo que está más cerca en términos de la distancia de ruta más corta hasta que llega al destino. Cuando se entiende de esta manera, queda claro cómo el algoritmo encuentra necesariamente 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 [ editar ]

En el siguiente algoritmo, 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 dist [ u ] . la longitud ( 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 18 es la longitud de la ruta desde el nodo raíz al nodo vecino v si fuera a pasar por u . Si esta ruta es más corta que la ruta más corta actual registrada para v, ese camino actual se reemplaza con este camino alternativo . La matriz anterior se rellena con un puntero al nodo "siguiente salto" en el gráfico de origen para obtener la ruta más corta al origen.

Una demostración del algoritmo de Dijkstra basado en la distancia euclidiana. Las líneas rojas son la ruta más corta que cubre, es decir, conectando u y prev [ u ]. Las líneas azules indican dónde ocurre la relajación, es decir, la conexión de vcon un nodo u en Q , que proporciona una ruta más corta desde la fuente a v.

1   función Dijkstra ( gráfico , fuente ):
 2
 3 crear conjunto de vértices Q
 4
 5       para cada vértice v en el gráfico :             
 6 dist [ v ] ← INFINIDAD                  
 7 prev [ v ] ← NO DEFINIDO                 
 8 agregar v a Q                       
10 dist [ fuente ] ← 0                        
11      
12       mientras que  Q no está vacío:
13           u ← vértice en Q con min dist [u]    
14                                              
15 removerte de Q 
dieciséis          
17           para cada vecino v de u :            // solo v que todavía están en Q 
18               alt ← dist [ u ] + longitud ( u , v )
19               si  alt v ]:               
20 dist [ v ] ← alt  
21 prev [ v ] ← u 
22
23       retorno dist [], anterior []

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

1   S ← secuencia vacía
2   u ← objetivo 
3   si se define prev [ u ] o  u = fuente :           // Haga algo solo si se puede alcanzar el vértice 
4       mientras  se define u :                        // Construya la ruta más corta con una pila S 
5 inserte u al comienzo de S         // Empuje el vértice en la pila 
6           u ← prev [ u ]                            // Recorrer del objetivo al origen

Ahora la secuencia S es la lista de vértices que constituyen una de las rutas más cortas desde el origen al destino , 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 el origen y el destino (puede haber varias rutas diferentes de la misma longitud). Luego, en lugar de almacenar solo un solo nodo en cada entrada de prev [] , almacenaríamos todos los nodos que satisfacen la condición de relajación. Por ejemplo, si tanto rcomo source se conectan con el objetivo y ambos se encuentran en diferentes rutas más cortas a través del objetivo (porque el costo de borde es el mismo en ambos casos), agregaríamos tanto r como source a prev [target ] . Cuando el algoritmo se complete, prev []la estructura de datos realmente 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, 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 realmente todas estas rutas más cortas entre dos nodos dados, usaríamos un algoritmo de búsqueda de rutas en el nuevo gráfico, como la búsqueda en profundidad .

Usando una cola de prioridad [ editar ]

Una cola de prioridad mínima es un tipo de datos abstracto que proporciona 3 operaciones básicas: add_with_priority () , disminuir_priority () y extract_min () . Como se mencionó anteriormente, el uso de dicha estructura de datos puede llevar a tiempos de computación más rápidos que el uso de una cola básica. En particular, el montón de Fibonacci ( Fredman y Tarjan 1984 ) 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 [ fuente ] ← 0                            // Inicialización
3
4 crear conjunto de vértices Q
5
6       para cada vértice v en el gráfico :           
7           si  v ≠ fuente 
8 dist [ v ] ← INFINITY                  // Distancia desconocida desde la fuente a v 
9 prev [ v ] ← NO DEFINIDA                     // Predecesora de v
10
11          Q .add_with_priority ( v , dist [ v ])
12
13
14      mientras que  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 :               // solo v que aún están en Q 
17              alt ← dist [ u ] + longitud ( u , v )
18              si  alt v ]
19 dist [ v ] ← alt 
20 prev [ v ] ← u 
21                  Q .decrease_priority ( v , alt )
22
23      de 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 la fuente ; luego, dentro del bloque if alt v ] , el nodo debe insertarse si aún no está en la cola (en lugar de realizar una operación de disminución de prioridad). ^[5] : 198

Se pueden utilizar otras estructuras de datos para lograr tiempos de computación aún más rápidos en la práctica. ^[14]

Prueba de corrección [ editar ]

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

Hipótesis invariante : para cada nodo visitado v , dist [v] se considera la distancia más corta desde la fuentea v ; y para cada nodo no visitado u , dist [u] se supone la distancia más corta cuando se viaja solo a través de los nodos visitados, desde la fuente hasta u . Esta suposición solo se considera si existe una ruta, de lo contrario, la distancia se establece en infinito. (Nota: no asumimos que dist [u] es la distancia real más corta para los nodos no visitados)

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

De lo contrario, asuma la hipótesis para n-1 nodos visitados. En cuyo caso, elegimos un borde vu donde u tiene la menor dist [u] de cualquier nodo no visitado y el borde vu es tal que dist [u] = dist [v] + longitud [v, u] . dist [u] se considera la distancia más corta desde la fuente hasta u porque si había un camino más corto, y si w fue el primer nodo no visitado en ese camino, entonces, por la hipótesis original dist [w] > dist [u] que crea una contradiccion Del mismo modo, si hubiera un camino más corto para usin utilizar nodos no visitados, y si el último nodo en ese camino fuera w , tendríamos dist [u] = dist [w] + longitud [w, u] , también una contradicción.

Después de procesar u , seguirá siendo cierto que para cada nodo no visitado w , dist [w] será la distancia más corta desde la fuente hasta w usando solo los nodos visitados, porque si hubiera una ruta más corta que no pase por u tendríamos lo encontré anteriormente, y si hubiera un camino más corto usando u , lo habríamos actualizado al procesar u .

Tiempo de ejecución [ editar ]

Los límites del tiempo de ejecución del algoritmo de Dijkstra en un gráfico con bordes E y vértices V se pueden expresar en función del número de bordes, denotado$${\ displaystyle | E |}, y el número de vértices, denotado $${\ displaystyle | V |}, utilizando la notación big-O . La estrechez posible de un límite depende de la forma en que se implementa el conjunto de vértices Q. En lo siguiente, los límites superiores se pueden simplificar porque$${\ displaystyle | E |} es $${\ displaystyle O (| V | ^ {2})} para cualquier gráfico, pero esa simplificación ignora el hecho de que en algunos problemas, otros límites superiores en $${\ displaystyle | E |}podra celebrar.

Para cualquier implementación del conjunto de vértices Q , el tiempo de ejecución está en

$${\ displaystyle O (| E | \ cdot T _ {\ mathrm {dk}} + | V | \ cdot T _ {\ mathrm {em}}),}

dónde $${\ displaystyle T _ {\ mathrm {dk}}} y $${\ displaystyle T _ {\ mathrm {em}}}son las complejidades de las operaciones de disminución de tecla y extracción mínima en Q , respectivamente. La implementación más sencilla del algoritmo de Dijkstra almacena el conjunto de vértices Qcomo una lista enlazada ordinaria o matriz, y extraer-mínimo es simplemente una búsqueda lineal a través de todos los vértices en Q . En este caso, el tiempo de ejecución es$${\ displaystyle O (| E | + | V | ^ {2}) = O (| V | ^ {2})}.

Se debe tener en cuenta que si la implementación almacena el gráfico como una lista de adyacencia, el tiempo de ejecución de un gráfico denso es decir $${\ displaystyle | E |} = $${\ displaystyle O (| V | ^ {2})} es

$${\ displaystyle \ Theta ((| V | ^ {2}) \ log | V |)}.

Para gráficos dispersos , es decir, gráficos con mucho menos que$${\ displaystyle | V | ^ {2}}En los bordes, 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 de búsqueda binaria de equilibrio automático , pila binaria , pila de pares o pila Fibonaccicomo una cola de prioridad para implementar la extracción del mínimo de manera eficiente. Para realizar eficientemente los pasos de reducción en un montón binario, es necesario usar una estructura de datos auxiliares 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 binaria auto-equilibrado o un montón binario, el algoritmo requiere

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

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

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

Cuando se usan montones binarios, la complejidad promedio de tiempo de caso es menor que en el peor de los casos: asumiendo que los costos de borde se dibujan independientemente de una distribución de probabilidadcomún , el número esperado de operaciones de tecla de disminución está delimitado por$${\ displaystyle O (| V | \ log (| E | / | V |))}, dando un tiempo total de ejecución de ^{[5] : 199–200}

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

Optimizaciones prácticas y gráficos infinitos [ editar ]

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 tecla de disminución, verifique si la clave está en la cola; es, disminuir su clave, de lo contrario insertarlo). ^[5] : 198 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, acelerando las operaciones de la cola. ^[7]

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 fuente única hasta el más cercano de un conjunto de nodos de destino en gráficos infinitos o aquellos que son demasiado grandes para representar en la memoria. El algoritmo resultante se denomina búsqueda de costo uniforme (UCS) en la literatura de inteligencia artificial ^{[7] [15] [16]} y se puede expresar en pseudocódigo como

 Procedimiento  UniformCostSearch (Graph, start, goal)
  nodo ← inicio
  costo ← 0
  frontera ← cola de prioridad que contiene solo el nodo
  explorado ← conjunto vacío
  hacer 
    si la frontera está vacía
       falla de retorno
    nodo ← frontier.pop ()
    Si el nodo es la solución de retorno de objetivo
      
    explored.add (nodo)
    para cada uno de los vecinos del nodo n
       si n no está en la exploración
          frontier.add (n)

La complejidad de este algoritmo se puede expresar de una manera alternativa para gráficos muy grandes: cuando C ^* es la longitud de la ruta más corta desde el nodo de inicio a cualquier nodo que satisfaga el predicado de "objetivo", cada borde ha costado al menos ε , y el número de vecinos por nodo está delimitada por b , entonces el tiempo del peor caso y el espacio del algoritmo de complejidad están ambos en O ( b ^{1 + ⌊ C * / varepsilon ⌋} ) . ^[15]

Las optimizaciones adicionales del algoritmo de Dijkstra para el caso de un solo objetivo incluyen variantes bidireccionales , variantes dirigidas por el objetivo, como el algoritmo A * (ver § Problemas y algoritmos relacionados ), gráficas de poda para determinar qué nodos probablemente formarán 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" seguidos por el cálculo de la ruta más corta entre estos nodos de tránsito utilizando una "autopista". ^{[17] Las} combinaciones de tales técnicas pueden ser necesarias para un desempeño práctico óptimo en problemas específicos.^[18]

Variantes especializadas [ editar ]

Cuando los pesos de arco son enteros pequeños (limitados por un parámetro C ), una cola de prioridad monótona se puede utilizar para acelerar el algoritmo de Dijkstra. El primer algoritmo de este tipo fue el algoritmo de Dial , que usó una cola de cubo para obtener un tiempo de ejecución$${\ displaystyle O (| E | + \ operatorname {diam} (G))}eso depende del diámetro ponderado de una gráfica con ponderaciones de borde entero ( Marcar 1969 ). El uso de un árbol de Van Emde Boas como la cola de prioridad trae la complejidad a$${\ displaystyle O (| E | \ log \ log C)}( Ahuja et al. 1990 ). Otra implementación interesante basada en la combinación de un nuevo montón de radix y el conocido Fibonacci se ejecuta en el tiempo$${\ displaystyle O (| E | + | V | {\ sqrt {\ log C}})}( Ahuja et al. 1990 ). Finalmente, los mejores algoritmos en este caso especial son los siguientes. El algoritmo dado por ( Thorup 2000 ) se ejecuta en$${\ displaystyle O (| E | \ log \ log | V |)}El tiempo y el algoritmo dado por ( Raman 1997 ) corre en$${\ displaystyle O (| E | + | V | \ min \ {(\ log | V |) ^ {1/3 + \ varepsilon}, (\ log C) ^ {1/4 + \ varepsilon} \}) } hora.

Además, para gráficos acíclicos dirigidos , es posible encontrar rutas más cortas desde un vértice inicial dado en lineal$${\ displaystyle O (| E | + | V |)}tiempo, procesando los vértices en un orden topológico y calculando la longitud de la trayectoria para cada vértice para que sea la longitud mínima obtenida a través de cualquiera de sus bordes entrantes. ^[19] [20]

En el caso especial de pesos enteros y gráficos conectados no dirigidos, el algoritmo de Dijkstra se puede contrarrestar completamente con un lineal $${\ displaystyle O (| E |)}algoritmo de complejidad, dado por ( Thorup 1999 ).

Problemas y algoritmos relacionados [ editar ]

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 óptimamente óptimas. Para obtener una lista clasificada de soluciones menos que óptimas, primero se calcula la solución óptima. Se elimina un borde único que aparece en la solución óptima 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 una nueva ruta más corta. 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 ponderaciones de borde negativas, siempre que el gráfico no contenga un ciclo negativo accesible 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 reduce cada vez que se recorre el ciclo. Es posible adaptar el algoritmo de Dijkstra para manejar los bordes de peso negativo al combinarlo con el algoritmo de Bellman-Ford (para eliminar los bordes negativos y detectar ciclos negativos), tal 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 se debe explorar, si hay información adicional disponible que proporciona un límite inferior en la "distancia" al objetivo. Este enfoque se puede ver desde la perspectiva de la programación lineal : existe un programa lineal natural para calcular las rutas más cortas , y las soluciones para su programa lineal dual son factibles si y solo si forman una heurística consistente (hablando aproximadamente, ya que las convenciones de signos difieren De un lugar a otro en la literatura). Esta factible heurística dual / consistente define una no negativa costo reducidoy A * esencialmente ejecuta el algoritmo de Dijkstra con estos costos reducidos. Si el dual satisface la condición más débil de admisibilidad , entonces A * es más parecido al algoritmo de Bellman-Ford.

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 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 primer lugar puede verse como un caso especial del algoritmo de Dijkstra en gráficos no ponderados, donde la cola de prioridad se degenera en una cola FIFO.

El método de marcha rápida se puede ver como una versión continua del algoritmo de Dijkstra que calcula la distancia geodésica en una malla de triángulo.

Perspectiva de la programación dinámica [ editar ]

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 de la ruta más corta mediante el método Reaching . ^{[21] [22] [23]}

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

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

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

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