O algoritmo de Dijkstra é un algoritmo para atopar os camiños máis curtos entre nós dun grafo ponderado, que pode representar, por exemplo, unha rede de estradas. Foi concibido polo informático Edsger W. Dijkstra en 1956 e publicado tres anos despois. «At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?»
O algoritmo de Dijkstra atopa o camiño máis curto desde un nó de orixe dado ata todos os demais nós. Pódese usar para atopar o camiño máis curto ata un nó de destino concreto, terminando o algoritmo tras determinar ese camiño. Por exemplo, se os nós do grafo representan cidades e os custos das arestas representan as distancias entre pares de cidades conectadas por unha estrada directa, o algoritmo de Dijkstra permite atopar a ruta máis curta entre unha cidade e todas as demais. Unha aplicación común dos algoritmos de camiño máis curto son os protocolos de encamiñamento de rede, en particular IS-IS e OSPF. Tamén se emprega como subrutina en algoritmos como o algoritmo de Johnson.
O algoritmo selecciona repetidamente o vértice coa menor distancia provisional. Unha implementación con busca linear do mínimo leva tempo. Cunha cola de prioridade de montículo de Fibonacci, a cota é . Esta cota non é óptima para o problema xeral: en 2025, Duan e colaboradores presentaron un algoritmo determinista de tempo para grafos dirixidos con pesos reais non negativos, no modelo de comparación e suma, que mellora a cota de Dijkstra en grafos dispersos.
Na formulación usual, os pesos das arestas deben ser non negativos: admítense tanto cero como valores positivos, enteiros ou reais. Esta condición garante que prolongar un camiño non reduce o seu custo. Unha xeneralización a outras etiquetas require condicións adicionais sobre a orde e a operación de extensión; unha orde parcial por si soa non abonda para aplicar o algoritmo presentado aquí.
En moitos campos, en particular a intelixencia artificial, o algoritmo de Dijkstra ou unha variante ofrece unha busca de custo uniforme e formúlase como unha instancia da idea máis xeral de busca best-first.
Historia «Cal é o camiño máis curto para viaxar de Rotterdam a Groningen, en xeral: dunha cidade dada a outra cidade dada. É o algoritmo para o camiño máis curto, que deseñei en vinte minutos. Unha mañá estaba comprando en Ámsterdam coa miña nova prometida e, cansos, sentámonos na terraza dun café a tomar un café e eu estaba a pensar se podería facelo, e entón deseñei o algoritmo para o camiño máis curto. Como dixen, foi unha invención de vinte minutos. De feito, publicouse no 59, tres anos despois. A publicación aínda é lexible; de feito, é bastante bonita. Unha das razóns de que sexa tan bonita é que a deseñei sen lapis nin papel. Despois aprendín que unha das vantaxes de deseñar sen lapis nin papel é que case se está forzado a evitar todas as complexidades evitables. Finalmente, ese algoritmo converteuse, para o meu gran asombro, nun dos piares da miña fama.» (tradución do inglés) — Edsger Dijkstra, nunha entrevista con Philip L. Frana, Communications of the ACM, 2001 (tradución do inglés)
Dijkstra pensou no problema do camiño máis curto mentres traballaba como programador no Centro Matemático de Ámsterdam en 1956. Quería demostrar as capacidades do novo ordenador ARMAC. O seu obxectivo era escoller un problema e unha solución informática que a xente allea á computación puidese entender. Deseñou o algoritmo do camiño máis curto e despois implementouno para ARMAC nun mapa de transporte simplificado de 64 cidades dos Países Baixos (limitouno a 64 para que 6 bits abondasen para codificar o número de cidade). Un ano despois, atopou outro problema exposto por enxeñeiros de hardware que traballaban no seguinte ordenador do instituto: minimizar a cantidade de cable necesaria para conectar os pinos do panel traseiro da máquina. Como solución, redescubriu o algoritmo da árbore de expansión mínima de Prim.
Algoritmo miniatura|alt=Progreso do algoritmo de Dijkstra nun problema de planificación de movemento.|Ilustración do algoritmo de Dijkstra atopando un camiño desde un nó de inicio (abaixo á esquerda, vermello) ata un nó obxectivo (arriba á dereita, verde) nun problema de planificación de movemento dun robot. O algoritmo require un nó de partida e calcula a distancia máis curta desde ese nó a cada un dos demais. Comeza con distancias infinitas e tenta melloralas paso a paso:
Créase un conxunto con todos os nós non visitados: o conxunto de non visitados. Asígnase a cada nó un valor de distancia desde a orixe: para o nó de partida é cero, e para todos os demais é infinito, xa que inicialmente non se coñece ningún camiño a eles. Durante a execución, a distancia dun nó N é a lonxitude do camiño máis curto descuberto ata o momento entre a orixe e N. Do conxunto de non visitados, escóllese como nó actual o que teña a menor distancia (finita); inicialmente, este é o nó de partida (distancia cero). Se o conxunto de non visitados está baleiro, ou só contén nós con distancia infinita (inalcanzables), o algoritmo remata saltando ao paso 6. Se só interesa o camiño a un nó obxectivo, o algoritmo remata en canto o nó actual sexa o obxectivo. Se non, continúa. Para o nó actual, considéranse todos os seus veciños non visitados e actualízanse as súas distancias a través do nó actual: compárase a distancia recentemente calculada coa asignada actualmente ao veciño e asígnaselle a menor. Por exemplo, se o nó actual A está marcado cunha distancia de 6 e a aresta que o une co seu veciño B ten lonxitude 2, a distancia a B a través de A é 6 + 2 = 8. Se B estaba marcado cunha distancia maior ca 8, actualízase a 8. Despois de considerar todos os veciños non visitados do nó actual, o nó actual quítase do conxunto de non visitados. Así, un nó visitado nunca se revisa, o que é correcto porque a distancia rexistrada no nó actual é mínima. Repítese desde o paso 3. Unha vez sae do bucle (pasos 3–5), cada nó visitado contén a súa distancia máis curta desde o nó de partida.
Descrición O camiño máis curto entre dúas interseccións dun mapa urbano pódese atopar con este algoritmo con lapis e papel. Cada intersección lístase nunha liña separada: unha é o punto de partida e etiquétase cunha distancia de 0. Todas as demais etiquétanse inicialmente cunha distancia infinita. En cada iteración, unha intersección convértese na actual; na primeira iteración, é o punto de partida.
Desde a intersección actual, avalíase a distancia a cada intersección veciña (directamente conectada) sumando a etiqueta da intersección actual e a distancia ao veciño e reetiquetando o veciño co menor desa suma e a súa etiqueta existente. É dicir, o veciño reetiquétase se o camiño a través da intersección actual é máis curto cós avaliados antes. Nese caso, márcase a estrada ao veciño cunha frecha que apunte a el e bórrase calquera outra frecha que apunte a el. Despois de avaliar as distancias aos veciños da intersección actual, esta márcase como visitada. A intersección non visitada coa menor etiqueta convértese na actual, e o proceso repítese ata que se visiten todos os nós con etiquetas menores cá do destino.
Unha vez non queden nós non visitados cunha etiqueta menor cá do destino, as frechas restantes amosan o camiño máis curto.
Pseudocódigo No pseudocódigo seguinte, dist é un vector que contén as distancias actuais desde a source aos demais vértices, é dicir, dist[u] é a distancia actual desde a orixe ao vértice u. O vector prev contén punteiros aos nós anteriores no camiño máis curto. A instrución u ← vertex in Q with min dist[u] busca o vértice u no conxunto Q co menor valor dist[u]. Graph.Distance(u,v) devolve a lonxitude da aresta que une os dous nós veciños u e v.
1 function Dijkstra(Graph, source): 2 Q ← empty set 3 for each vertex v in Graph.Vertices: 4 dist[v] ← INFINITY 5 prev[v] ← UNDEFINED 6 add v to Q 7 dist[source] ← 0 8 9 while Q is not empty: 10 u ← vertex in Q with minimum dist[u] 11 Q.remove(u) 12 13 for each outgoing edge (u, v) of u: 14 alt ← dist[u] + Graph.Distance(u,v) 15 if alt < dist[v]: 16 dist[v] ← alt 17 prev[v] ← u 18 19 return dist[], prev[]
Para atopar o camiño máis curto entre a source e un target, a busca remata despois da liña 10 se u = target. O camiño máis curto desde a source ao target pódese obter por iteración inversa:
1 S ← empty sequence 2 u ← target 3 if prev[u] is defined or u = source: // Proseguir se o vértice é alcanzable 4 while u is defined: // Construír o camiño máis curto coa pila S 5 S.push(u) // Apilar o vértice 6 u ← prev[u] // Percorrer do destino á orixe
Agora S é a lista de vértices que constitúen un dos camiños máis curtos desde a source ao target, ou a secuencia baleira se non existe ningún camiño.
Usar unha cola de prioridade Unha cola de prioridade mínima é un tipo de dato abstracto que fornece tres operacións básicas: add_with_priority(), decrease_priority() e extract_min(). Un montículo de Fibonacci ou a cola de Brodal ofrecen implementacións óptimas para esas tres operacións.
1 function Dijkstra(Graph, source): 2 Q ← Queue storing vertex priority 3 4 dist[source] ← 0 // Inicialización 5 Q.add_with_priority(source, 0) // prioridade asociada = dist[·] 6 prev[source] ← UNDEFINED 7 for each vertex v in Graph.Vertices: 8 if v ≠ source 9 prev[v] ← UNDEFINED // Predecesor de v 10 dist[v] ← INFINITY // Distancia descoñecida da orixe a v 11 Q.add_with_priority(v, INFINITY) 12 13 14 while Q is not empty: // Bucle principal 15 u ← Q.extract_min() // Retirar e devolver o mellor vértice 16 for each outgoing edge (u, v) of u: // Percorrer os veciños saíntes de u 17 alt ← dist[u] + Graph.Distance(u,v) 18 if alt < dist[v]: 19 prev[v] ← u 20 dist[v] ← alt 21 Q.decrease_priority(v, alt) 22 23 return (dist, prev)
Corrección Para probar a corrección do algoritmo de Dijkstra pódese usar a indución matemática sobre o número de nós visitados.
Hipótese invariante: despois de relaxar as arestas dos nós visitados, dist[v] é a distancia definitiva de cada nó visitado v. Para cada nó non visitado u, dist[u] é o menor custo dun camiño cuxos vértices anteriores a u xa foron visitados, ou infinito se non existe.
Caso base No caso base procésase a source, de distancia cero, e reláxanse todas as súas arestas saíntes. Os veciños reciben o menor custo dunha aresta directa desde a orixe e os demais conservan infinito. Así cúmprese a invariante.
Indución Supoñendo que a hipótese se cumpre para nós visitados, para amosar que se cumpre para , sexa u o seguinte nó visitado, é dicir, o de mínimo dist[u]. Afírmase que dist[u] é a distancia máis curta desde a source a u. A proba é por redución ao absurdo. Se existise un camiño máis curto, ese camiño contería outro nó non visitado ou non.
No primeiro caso, sexa w o primeiro nó non visitado dese camiño, anterior a u. Pola invariante, dist[w] non supera o custo do prefixo ata w. O resto do camiño ten custo non negativo, polo que o camiño completo custa polo menos dist[w]. Como se escolleu u co mínimo valor provisional, dist[u] ≤ dist[w]. Isto contradí que o camiño completo sexa máis curto ca dist[u]. No segundo caso, sexa w o penúltimo nó do camiño máis curto. Iso significa dist[w] + Graph.Edges[w,u] < dist[u], unha contradición porque cando se visitou w debería ter fixado dist[u] a un valor non maior ca dist[w] + Graph.Edges[w,u].
Despois de procesar u, segue sendo certo que para cada nó non visitado w, dist[w] é a distancia máis curta desde a source a w usando só nós visitados. Cando todos os nós estean visitados, o camiño máis curto desde a source a calquera nó v consta só de nós visitados; por tanto, dist[v] é a distancia máis curta.
Tempo de execución