El algoritmo de Dijkstra ( / d aɪ k s t r ə z / DYKE -strəz ) 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. [4] [5] [6]
Clase | Algoritmo de búsqueda Algoritmo codicioso Programación dinámica [1] |
---|---|
Estructura de datos | Gráfico Se suele utilizar con cola de prioridad / montón para optimización [2] [3] |
Rendimiento en el peor de los casos | [3] |
El algoritmo existe en muchas variantes. El algoritmo original de Dijkstra encontró la ruta más corta entre dos nodos dados, [6] pero una variante más común fija un solo nodo como el nodo "fuente" y encuentra las rutas más cortas desde la fuente a todos los demás nodos en el gráfico, produciendo una ruta más corta árbol .
Para un nodo de origen determinado en el gráfico, el algoritmo encuentra la ruta más corta entre ese nodo y todos los demás. [7] : 196–206 También se puede utilizar para encontrar las rutas más cortas de 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 ruta del borde representan distancias de conducción entre pares de ciudades conectadas por una carretera directa (para simplificar, ignore las luces rojas, las señales de alto, las carreteras de peaje y otras obstrucciones), se puede utilizar 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 , más notablemente IS-IS (Intermediate System to Intermediate System) y Open Shortest Path First ( OSPF ). 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 el uso de etiquetas que estén parcialmente ordenadas , siempre que las etiquetas posteriores (se produce una etiqueta posterior al atravesar un borde) sean monótonamente no decrecientes. Esta generalización se denomina algoritmo genérico de ruta más corta de Dijkstra. [8]
El algoritmo de Dijkstra utiliza una estructura de datos para almacenar y consultar soluciones parciales ordenadas por distancia desde el inicio. Mientras que el algoritmo original usa una cola de prioridad mínima y se ejecuta a tiempo (dónde es el número de nodos y es el número de aristas), también se puede implementar en usando una matriz. La idea de este algoritmo también se da en Leyzorek et al. 1957 . Fredman & Tarjan 1984 proponen el uso de una cola de prioridad mínima del montón de Fibonacci para optimizar la complejidad del tiempo de ejecución para. 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 no negativos ilimitados. Sin embargo, los casos especializados (como pesos limitados / enteros, gráficos acíclicos dirigidos, etc.) se pueden mejorar aún más como se detalla en Variantes especializadas . Además, si se permite el preprocesamiento, los algoritmos como las jerarquías de contracción pueden ser hasta siete órdenes de magnitud más rápidos.
En algunos campos, la inteligencia artificial en particular, el algoritmo de Dijkstra o una variante del mismo se conoce como búsqueda de costo uniforme y se formula como una instancia de la idea más general de la búsqueda del mejor primero . [9]
Historia
¿Cuál es el camino más corto para viajar de Rotterdam a Groningen , en general: de una ciudad determinada a una ciudad determinada? Es el algoritmo para el camino más corto , que diseñé en unos veinte minutos. Una mañana estaba de compras en Ámsterdam con mi joven prometida y, cansado, nos sentamos en la terraza del café a tomar una taza de café y estaba pensando si podía hacer esto, 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, de hecho, es bastante agradable. Una de las razones por las que es tan bonito fue que lo diseñé sin lápiz y papel. Más tarde supe que una de las ventajas de diseñar sin lápiz y papel es que uno está 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 Mathematical Center en Amsterdam en 1956 como programador para demostrar las capacidades de una nueva computadora llamada ARMAC. [10] Su objetivo era elegir tanto un problema como una solución (que sería producida por computadora) que las personas que no usaban 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, por lo que 6 bits serían suficientes para codificar el número de ciudad). [5] Un año después, se encontró con otro problema de los ingenieros de hardware que trabajaban en la próxima computadora del instituto: minimizar la cantidad de cable necesario para conectar los pines en el panel posterior de la máquina. Como solución, redescubrió el algoritmo conocido como algoritmo de árbol de expansión mínimo de Prim (conocido anteriormente por Jarník y también redescubierto por Prim ). [11] [12] Dijkstra publicó el algoritmo en 1959, dos años después de Prim y 29 años después de Jarník. [13] [14]
Algoritmo
Dejemos que el nodo en el que estamos comenzando 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.
- Marque todos los nodos como no visitados. Cree un conjunto de todos los nodos no visitados denominado conjunto no visitado .
- Asigne a cada nodo un valor de distancia tentativo: configúrelo en cero para nuestro nodo inicial y en infinito para todos los demás nodos. Establezca el nodo inicial como actual. [15]
- Para el nodo actual, considere 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 más pequeño. 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 una longitud de 2, entonces la distancia de B a través de A será 6 + 2 = 8. Si B se marcó previamente con una distancia superior a 8 y luego cámbielo a 8. De lo contrario, se mantendrá el valor actual.
- 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 . Un nodo visitado nunca se volverá a comprobar.
- 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 (al planificar un recorrido completo; ocurre cuando no hay conexión entre el nodo inicial y nodos no visitados restantes), luego deténgase. El algoritmo ha terminado.
- 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.
Al planificar una ruta, en realidad no es necesario esperar hasta que el nodo de destino sea "visitado" como se indicó anteriormente: el algoritmo puede detenerse una vez que el nodo de destino tenga la distancia tentativa más pequeña entre todos los nodos "no visitados" (y por lo tanto podría seleccionarse como el siguiente "actual").
Descripción
Suponga que le gustaría 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) a cualquier otra intersección en el mapa con infinito . Esto no se hace para implicar 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 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 a ella (la etiqueta de la intersección) será cero . Para iteraciones posteriores (después de la primera), la intersección actual será una intersección no visitada más cercana al punto de partida (esto será fácil de encontrar).
Desde la intersección actual, actualice la distancia a cada intersección no visitada que esté conectada directamente 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. En efecto, la intersección se vuelve a etiquetar si la ruta a ella a través de la intersección actual es más corta que las rutas conocidas anteriormente. Para facilitar la identificación del camino más corto, en lápiz, marque el camino con una flecha apuntando a la intersección reetiquetada si la etiqueta / reetiquete, y borre todos los demás que apunten a ella. Después de haber actualizado las distancias a cada intersección vecina , marque la intersección actual como visitada y seleccione una intersección no visitada con 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 la ruta más corta desde el punto de partida hasta ella y no se volverán a visitar ni volver a visitar.
Continúe este proceso de actualización de las intersecciones vecinas con las distancias más cortas, marcando la intersección actual como visitada y moviéndose a una intersección no visitada más cercana hasta que haya marcado el destino como visitado. Una vez que haya marcado el destino como visitado (como es el caso de cualquier intersección visitada), habrá determinado el camino más corto hacia él desde el punto de partida y podrá rastrear 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 ha llegado al nodo de destino) siguiendo a los padres de los nodos desde el nodo de destino hasta el nodo de inicio; es por eso que también realizamos un seguimiento del padre de cada nodo.
Este algoritmo no hace ningún intento de "exploración" directa hacia el destino como cabría esperar. Más bien, la única consideración para determinar la próxima intersección "actual" es su distancia desde el punto de partida. Por lo tanto, este algoritmo se expande hacia afuera desde el punto de partida, considerando interactivamente cada nodo que está más cerca en términos de distancia de ruta más corta hasta que alcanza el 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 algoritmo de pseudocódigo , 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 menos valor dist [ u ] . length ( u , v ) devuelve la longitud del borde que une (es decir, la distancia entre) los dos nodos vecinos tu 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 tuviera que pasar u . Si esta ruta es más corta que la ruta más corta actual registrada para v , esa ruta actual se reemplaza con esta ruta alternativa . La La matriz prev se rellena con un puntero al nodo "siguiente salto" en el gráfico fuente para obtener la ruta más corta a la fuente.
1 función Dijkstra ( Gráfico , fuente ): 2 3 crear el conjunto de vértices Q 4 5 para cada vértice v en Graph : 6 dist [ v ] ← INFINITO 7 prev [ v ] ← INDEFINIDO 8 agregar v a Q 9 dist [ fuente ] ← 0 10 11 mientras Q no está vacío:12 u ← vértice en Q con min dist [u] 13 14 quita u de Q15 16 para cada vecino v de u : // solo v que todavía están en Q 17 alt ← dist [ u ] + length ( u , v )18 si altv ]: 19 dist [ v ] ← alt 20 prev [ v ] ← u2122 return dist [], anterior []
Si solo nos interesa un camino más corto entre vértices fuente y objetivo , podemos terminar la búsqueda después de la línea 15 si u = objetivo . Ahora podemos leer el camino más corto desde fuente a objetivo por 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 accesible 4 mientras u está definido: // Construye la ruta más corta con una pila S 5 inserta u al principio de S // Empuja el vértice hacia la pila 6 u ← prev [ u ] // Recorre desde el destino hasta la fuente
Ahora secuencia S es la lista de vértices que constituyen uno de los caminos más cortos desde fuente a destino , o la secuencia vacía si no existe una ruta.
Un problema más general sería encontrar todos los caminos más cortos entre fuente y target (puede haber varios diferentes de la misma longitud). Entonces, 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 ambos r y fuente conectar a objetivo y ambos se encuentran en diferentes caminos más cortos a través de objetivo (porque el costo de borde es el mismo en ambos casos), entonces agregaríamos ambos r y fuente a prev [ objetivo ] . Cuando se completa el algoritmo, La estructura de datos prev [] 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
Una cola de prioridad mínima es un tipo de datos abstracto que proporciona 3 operaciones básicas: add_with_priority () , disminución_prioridad () y extract_min () . Como se mencionó anteriormente, el uso de una estructura de datos de este tipo puede conducir a tiempos de cómputo 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ón34 crear cola de prioridad de vértice Q56 para cada vértice v en Graph : 7 if v ≠ source 8 dist [ v ] ← INFINITY // Distancia desconocida de la fuente a v 9 prev [ v ] ← UNDEFINED // Predecesor de v1011 Q .add_with_priority ( v , dist [ v ])121314 mientras Q no está vacío: // El bucle principal 15 u ← Q .extract_min () // Elimina y devuelve el mejor vértice 16 para cada vecino v de u : // solo v que todavía están en Q 17 alt ← dist [ u ] + longitud ( u , v )18 si altv ]19 dist [ v ] ← alt 20 prev [ v ] ← u 21 Q .decrease_priority ( v , alt )2223 volver 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 la fuente ; luego, dentro del bloque, la disminución_prioridad se convierte en una operación agregar_con_prioridad si el nodo aún no está en la cola. [7] : 198if 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 aún no se haya encontrado una conexión más corta. Esto se puede hacer extrayendo adicionalmente la prioridad asociada p
de la cola y solo procesando más dentro del ciclo. [dieciséis]if p == dist[u]
while Q is not empty
Estas alternativas pueden utilizar colas de prioridad totalmente basadas en arreglos sin la funcionalidad de disminució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 gráficos más densos. [17]
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 v , dist [v] es la distancia más corta desde fuente a v cuando se viaja solo a través de nodos visitados, o infinito si no existe tal ruta. (Nota: no asumimos dist [v] es la distancia más corta real para los nodos no visitados).
El caso base es cuando solo hay un nodo visitado, a saber, el nodo inicial fuente , en cuyo caso la hipótesis es trivial .
De lo contrario, asuma la hipótesis de n-1 nodos visitados. En cuyo caso, elegimos una ventaja. vu donde tu tienes lo menos dist [u] de los nodos no visitados y el borde vu es tal que dist [u] = dist [v] + longitud [v, u] . dist [u] se considera la distancia más corta desde fuente a u porque si hubiera un camino más corto, y si w fue el primer nodo no visitado en ese camino luego por la hipótesis original dist [w] > dist [u] que crea una contradicción. Del mismo modo, si hubiera un camino más corto para u sin utilizar nodos no visitados, y si el último nodo de esa ruta fuera w , entonces habríamos tenido 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 fuente a w usando solo los nodos visitados, porque si hubiera una ruta más corta que no pasa u lo habríamos encontrado anteriormente, y si hubiera una ruta más corta 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
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 en función del número de aristas, denotado, y el número de vértices, denotado , usando la notación Big-O . El límite de complejidad depende principalmente de la estructura de datos utilizada para representar el conjunto Q . A continuación, los límites superiores se pueden simplificar porque es para cualquier gráfico, pero esa simplificación ignora el hecho de que en algunos problemas, otros límites superiores en podra celebrar.
Para cualquier estructura de datos para el conjunto de vértices Q , el tiempo de ejecución está en [2]
dónde y son las complejidades de las operaciones de disminución de clave y extracción de mínimo en Q , respectivamente. La versión más simple de tiendas el algoritmo de Dijkstra el vértice definido Q como una lista ordinaria vinculado o matriz, y el extracto-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.
Si el gráfico se almacena como una lista de adyacencia, el tiempo de ejecución de un gráfico denso (es decir, donde ) es
- .
Para gráficos dispersos , es decir, gráficos con mucho menos debordes, el algoritmo de Dijkstra se pueden implementar de manera más eficiente mediante el almacenamiento de la gráfica en forma de listas de adyacencia y usando un árbol binario de búsqueda auto-equilibrio , pila binaria , el emparejamiento del montón o pila de Fibonacci como una cola de prioridad para implementar la extracción mínima eficaz. Para realizar los pasos de disminución de clave en un montón binario de manera eficiente, es necesario utilizar una estructura de datos auxiliar que mapee cada vértice a su posición en el montón, y para mantener esta estructura actualizada a medida que cambia la cola de prioridad Q. Con un árbol de búsqueda binario autoequilibrado o un montón binario, el algoritmo requiere
tiempo en el peor de los casos (donde denota el logaritmo binario ); para gráficos conectados, este límite de tiempo se puede simplificar a. El montón de Fibonacci mejora esto para
Cuando se utilizan montones binarios, la complejidad del tiempo promedio del caso 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, dando un tiempo de ejecución total de [7] : 199-200
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 disminución de clave, verifique si la clave está en la cola; si es, disminuya su clave, de lo 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. [9]
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 de destino en gráficos infinitos o aquellos demasiado grandes para representarlos en la memoria. El algoritmo resultante se denomina búsqueda de costo uniforme (UCS) en la literatura sobre inteligencia artificial [9] [18] [19] y puede expresarse en pseudocódigo como
procedimiento uniform_cost_search (Graph, start, goal) es nodo ← inicio costo ← 0 frontera ← cola de prioridad que contiene solo el nodo explorado ← conjunto vacío hacer si la frontera está vacía entonces devuelve el fracaso nodo ← frontera.pop () si el nodo es el objetivo , devuelve la solución explored.add (nodo) para cada uno de los vecinos del nodo n hacer si n no está explorado, entonces 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 inicial hasta cualquier nodo que satisfaga el predicado "objetivo", cada borde tiene un costo de al menos ε , y el número de vecinos por nodo está limitado por b , entonces el tiempo y la complejidad del espacio en el peor de los casos del algoritmo están en O ( b 1 + ⌊ C * ⁄ ε ⌋ ) . [18]
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 las rutas más cortas (enrutamiento basado en alcance), y descomposiciones jerárquicos del gráfico de entrada que reducen s - t enrutamiento para la conexión de s y t a sus respectivos " nodos de tránsito ", seguido de cálculo de ruta más corta entre estos nodos de tránsito utilizando un "autopista". [20] Pueden ser necesarias combinaciones de tales técnicas para un desempeño práctico óptimo en problemas específicos. [21]
Variantes especializadas
Cuando los pesos de arco son números enteros pequeños (delimitados por un parámetro ), las 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 enteros positivos, que usa una cola de cubos para obtener un tiempo de ejecución.. El uso de un árbol de Van Emde Boas como cola de prioridad aporta complejidad a( Ahuja et al. 1990 ). Otra variante interesante basada en una combinación de un nuevo montón de radix y el conocido montón de Fibonacci se ejecuta en el tiempo( Ahuja et al. 1990 ). Finalmente, los mejores algoritmos en este caso especial son los siguientes. El algoritmo dado por ( Thorup 2000 ) se ejecuta entiempo y el algoritmo dado por ( Raman 1997 ) se ejecuta en hora.
Problemas y algoritmos relacionados
La funcionalidad del algoritmo original de Dijkstra se puede ampliar con una variedad de modificaciones. Por ejemplo, a veces es deseable presentar soluciones que no sean ó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 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 de algoritmo de Dijkstra, el algoritmo Bellman-Ford se puede utilizar en gráficos con pesos de las aristas negativas, siempre que el gráfico no contiene ningún ciclo negativo accesible desde la fuente vértice s . La presencia de tales ciclos significa que no hay un camino más corto, ya que el peso total disminuye cada vez que se atraviesa el ciclo. (Esta afirmación asume que una "ruta" puede repetir vértices. En teoría de grafos, esto normalmente no está permitido. En informática teórica a menudo está permitido.) Es posible adaptar el algoritmo de Dijkstra para manejar los bordes de peso negativos combinándolo con el algoritmo de Bellman-Ford (para eliminar los 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. Este enfoque puede verse desde la perspectiva de la programación lineal : existe un programa lineal natural para calcular las rutas más cortas , y las soluciones a su programa lineal dual son factibles si y solo si forman una heurística consistente (hablando en términos generales, ya que las convenciones de signos difieren de un lugar a otro en la literatura). Esta factible heurística dual / consistente define un costo reducido no negativo y A * esencialmente está ejecutando 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 del gráfico; Dijkstra se ocupa de solo 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 primero 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 programación dinámica para el problema del camino más corto mediante el método Reaching . [22] [23] [24]
De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, [25] a saber
Problema 2. Encuentra la ruta de longitud total mínima entre dos nodos dados. y .
Usamos el hecho de que, si es un nodo en la ruta mínima desde a , el conocimiento de este último implica el conocimiento del camino mínimo desde a .
es una paráfrasis del famoso Principio de Optimidad 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 de larga distancia óptimos en Etiopía y contrastarlos con la situación en el suelo. [26]
Ver también
- Algoritmo de búsqueda A *
- Algoritmo de Bellman-Ford
- Camino más corto euclidiano
- Relleno de inundación
- 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
- ^ Controvertido, véase Moshe Sniedovich (2006). "El algoritmo de Dijkstra revisitado: la conexión de programación dinámica" . Control y Cibernética . 35 : 599–620.y por debajo de la parte .
- ^ a b Cormen y col. 2001
- ^ a b Fredman y Tarjan 1987
- ^ Richards, Hamilton. "Edsger Wybe Dijkstra" . Premio AM Turing . Asociación de Maquinaria Informática . 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 una audiencia no técnica: Dada una red de carreteras que conectan ciudades, ¿cuál es la ruta más corta entre dos ciudades designadas?
- ^ a b c Frana, Phil (agosto de 2010). "Una entrevista con Edsger W. Dijkstra" . Comunicaciones de la ACM . 53 (8): 41–47. doi : 10.1145 / 1787234.1787249 .
- ^ a b Dijkstra, EW (1959). "Una nota sobre dos problemas relacionados con los gráficos" (PDF) . Numerische Mathematik . 1 : 269-271. doi : 10.1007 / BF01386390 . S2CID 123284777 .
- ^ a b c d Mehlhorn, Kurt ; Sanders, Peter (2008). "Capítulo 10. Rutas más cortas" (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.
- ^ 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 .
- ^ a b c Felner, Ariel (2011). Documento de posición: algoritmo de Dijkstra versus búsqueda de costos uniformes o un caso en contra del algoritmo de Dijkstra . Proc. 4th Int'l Symp. sobre la búsqueda combinatoria. En un problema de búsqueda de ruta, Felner descubre que la cola puede ser un factor 500-600 más pequeña, ocupando alrededor del 40% del tiempo de ejecución.
- ^ "ARMAC" . Héroes anónimos en la historia de la informática holandesa . 2007. Archivado desde el original el 13 de noviembre de 2013.
- ^ Dijkstra, Edsger W., Reflexiones sobre "Una nota sobre dos problemas relacionados con gráficos (PDF)
- ^ Tarjan, Robert Endre (1983), Estructuras de datos y algoritmos de red , CBMS_NSF Regional Conference Series in Applied Mathematics, 44 , Society for Industrial and Applied Mathematics, p. 75,
El tercer algoritmo clásico de árbol de expansión mínimo fue descubierto por Jarník y redescubierto por Prim y Dikstra; se conoce comúnmente como algoritmo de Prim.
- ^ Prim, RC (1957). "Redes de conexión más cortas y algunas generalizaciones" (PDF) . Revista técnica de Bell System . 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 .
- ↑ V. Jarník: O jistém problému minimálním [Acerca de cierto problema mínimo], Práce Moravské Přírodovědecké Společnosti, 6, 1930, págs. 57–63. (en checo)
- ^ Gass, Saul; Fu, Michael (2013). Gass, Saul I; Fu, Michael C (eds.). "Algoritmo de Dijkstra". Enciclopedia de Investigación de Operaciones y Ciencias de la Gestión . Saltador. 1 . doi : 10.1007 / 978-1-4419-1153-7 . ISBN 978-1-4419-1137-7 - a través de Springer Link.
- ^ Observe que p
u ] nunca se puede mantener 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. - ^ Chen, M .; Chowdhury, RA; Ramachandran, V .; Roche, DL; Tong, L. (2007). Colas de prioridad y algoritmo de Dijkstra - Informe técnico de UTCS TR-07-54 - 12 de octubre de 2007 (PDF) . Austin, Texas: Universidad de Texas en Austin, Departamento de Ciencias de la Computación.
- ^ a b Russell, Stuart ; Norvig, Peter (2009) [1995]. Inteligencia artificial: un enfoque moderno (3ª ed.). Prentice Hall. págs. 75, 81. ISBN 978-0-13-604259-4.
- ^ A veces también búsqueda de menor costo : Nau, Dana S. (1983). "Sistemas informáticos expertos" (PDF) . Computadora . IEEE. 16 (2): 63–85. doi : 10.1109 / mc.1983.1654302 .
- ^ Wagner, Dorothea; Willhalm, Thomas (2007). Técnicas de aceleración para cálculos de ruta más corta . STACS. págs. 23–36.
- ^ Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea (2010). "Combinando técnicas de aceleración jerárquicas y dirigidas a objetivos para el algoritmo de Dijkstra" . J. Algoritmos experimentales . 15 : 2.1. doi : 10.1145 / 1671970.1671976 . S2CID 1661292 .
- ^ Sniedovich, M. (2006). "El algoritmo de Dijkstra revisitado: 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 trabajo con módulos computacionales interactivos.
- ^ Denardo, EV (2003). Programación dinámica: modelos y aplicaciones . Mineola, NY: Publicaciones de Dover . ISBN 978-0-486-42810-9.
- ^ Sniedovich, M. (2010). Programación dinámica: fundamentos y principios . Francis y Taylor . ISBN 978-0-8247-4099-3.
- ↑ Dijkstra , 1959 , p. 270
- ^ Nyssen, J., Tesfaalem Ghebreyohannes, Hailemariam Meaza, Dondeyne, S., 2020. Exploración de un mapa africano medieval (Aksum, Etiopía) - ¿Cómo encajan los mapas históricos con la topografía? En: De Ryck, M., Nyssen, J., Van Acker, K., Van Roy, W., Liber Amicorum: Philippe De Maeyer In Kaart. Wachtebeke (Bélgica): University Press: 165-178.
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.). MIT Press y McGraw – Hill . págs. 595–601. ISBN 0-262-03293-7.
- Dial, 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 de optimización de red mejorados". Revista de la Asociación de Maquinaria Informática . 34 (3): 596–615. doi : 10.1145 / 28869.28874 . S2CID 7904683 .
- Zhan, F. Benjamin; Noon, Charles E. (febrero de 1998). "Algoritmos de ruta más corta: una evaluación utilizando redes 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, Enfermera registrada (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 de la ruta más corta" (PDF) . Revista de la ACM . 37 (2): 213-223. doi : 10.1145 / 77600.77615 . hdl : 1721,1 / 47994 . S2CID 5499589 .
- Raman, Rajeev (1997). "Resultados recientes sobre el problema de las rutas más cortas de una sola fuente". 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 direccionadas 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
- Explicación gráfica del algoritmo de Dijkstra paso a paso en un ejemplo , Gilles Bertrand