Algoritmo de Dijkstra
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]
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 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 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 de los algoritmos de ruta más corta son los protocolos de enrutamiento de red , sobre todo 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 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. 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 mediante el uso de 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 . Este es asintóticamente el algoritmo de ruta más corta de fuente única más rápido conocido para gráficos dirigidos arbitrarioscon ponderaciones no negativas ilimitadas. 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.
