Algoritmo de Dijkstra
El algoritmo de Dijkstra ( / d aɪ k s t r ə z / DYKE -strəz ) es un algoritmo para encontrar los caminos más cortos entre nodos en un gráfico , que puede representar, por ejemplo, redes de carreteras . Fue concebido por el informático Edsger W. Dijkstra en 1956 y publicado tres años después. [4] [5] [6]
El algoritmo 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 fuente dado en el gráfico, el algoritmo encuentra el camino más corto entre ese nodo y todos los demás. [7] : 196–206 También se puede usar para encontrar las rutas más cortas desde un solo nodo a un solo nodo de destino al detener 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 de 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 con 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 de algoritmos de ruta más corta son los protocolos de enrutamiento de red , más notablemente IS-IS(Sistema intermedio a sistema intermedio) 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 números 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 al atravesar un borde) sean monotónicamente 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 principio. Si bien el algoritmo original usa una cola de prioridad mínima y se ejecuta en el tiempo (donde está el número de nodos y el número de bordes), también se puede implementar usando una matriz. La idea de este algoritmo también se da en Leyzorek et al. 1957 . Fredman & Tarjan 1984 proponen usar una cola de prioridad mínima de montón de Fibonacci para optimizar la complejidad del tiempo de ejecución a . Este es asintóticamente el algoritmo de ruta más corta de fuente única más rápido conocido para gráficos dirigidos arbitrarioscon pesos ilimitados no negativos. Sin embargo, los casos especializados (como pesos acotados/enteros, gráficos acíclicos dirigidos, etc.) pueden mejorarse aún más, como se detalla en Variantes especializadas . Además, si se permite el preprocesamiento, los algoritmos, como las jerarquías de contracción, pueden ser hasta siete órdenes de magnitud más rápidos.
