Algoritme de Dijkstra

El algoritme de Dijkstra, també cridat algoritme de camins mínims, és un algoritme per a la determinació del camí més curt, donat un vèrtiç orige, cap al restant dels vèrtiços en un grafo que té pesos en cada aresta. El seu nom aludix a Edsger Dijkstra, científic de la computació dels Països Baixos que ho va concebre en 1956 i ho va publicar per primera volta en 1959.^[1]^[2]

L'idea subjacent en este algoritme consistix en anar explorant tots els camins més curts que partixen del vèrtiç orige i que duen a tots els demés vèrtiços; quan s'obté el camí més curt des del vèrtiç orige fins al restant dels vèrtiços que componen el grafo, l'algoritme es deté. Es tracta d'una especialisació de la busca de cost uniforme i, com a tal, no funciona en grafos en arestes de cost negatiu (en elegir sempre el nodo en distància menor, poden quedar exclosos de la busca nodos que en pròximes iteraciones baixarien el cost general del camí en passar per una aresta en cost negatiu).^[3]

Algoritme

Tenint un grafo dirigit ponderat de $N$ nodos no aïllats, siga $x$ el nodo inicial. Un vector $D$ de tamany $N$ guardarà al final de l'algoritme les distàncies des de $x$ fins al restant dels nodos.

Inicializar totes les distàncies en $D$ en un valor infinit relatiu, ya que són desconegudes al principi, exceptuant la de $x$ , que es deu colocar en $0$ , degut a que la distància de $x$ a $x$ seria $0$ .
Siga $a = x$ (Es pren $a$ com a nodo actual).
Es recorren tots els nodos adjacents de a, llevat els nodos marcats. Se'ls cridarà nodos no marcats v_i.
Per al nodo actual, es calcula la distancia tentativa des de dit nodo fins als seus veïns en la següent fòrmula: dt(v_i) = D_a + d(a,v_i). És dir, la distancia tentativa del nodo ‘v_i’ és la distància que actualment té el nodo en el vector D més la distància des de dit nodo ‘a’ (l'actual) fins al nodo v_i. Si la distancia tentativa és menor que la distància almagasenada en el vector, llavors s'actualisa el vector en esta distancia tentativa. És dir, si dt(v_i) < D_{vaig vore} → D_{vaig vore} = dt(v_i)
Es marca com a complet el nodo a.
Es pren com a pròxim nodo actual el de menor valor en D (pot fer-se almagasenant els valors en una coa de prioritat) i es retorna al pas 3, mentres existixquen nodos no marcats.

Una volta terminat a l'algoritme, $D$ estarà completament ple.

Complexitat

Orde de complexitat de l'algoritme:

O(|V|²+|A|) = O(|V|²), sense utilisar coa de prioritat, :O((|A|+|V|) log |V|) = O(|A| log |V|) utilisant coa de prioritat (per eixemple, un montícul binario o un arbre binario balancejat). Per un atre costat, si s'utilisa un montícul de Fibonacci, seria O(|V| log |V|+|A|).

La complexitat computacional de l'algoritme de Dijkstra es pot calcular contant les operacions realisades:

l'algoritme consistix en n-1 iteraciones, com a màxim. En cada iteración, s'afig un vèrtiç al conjunt distinguit.
En cada iteración, s'identifica el vèrtiç en la menor etiqueta entre els que no estan en S_k. El número d'estes operacions està acotat per n-1.
Ademés, es realisen una suma i una comparació per a actualisar l'etiqueta de cada u dels vèrtiços que no estan en S_k.

Després, en cada iteración es realisen com a molt 2(n-1) operacions.

Llavors:

Teorema: L'algoritme de lpz realisa O(n²) operacions (sumes i comparacions) per a determinar la llongitut del camí més curt entre dos vèrtiços d'un grafo ponderat simple, conexo i no dirigit en n vèrtiços.

En general:

Temps d'eixecució = O(|A|.𝑻_𝒅𝒌+|v|.𝑻_𝒅𝒎)

|A|: Número d'arestes

𝑻_𝒅𝒌: Complexitat de disminuir clau

|V|: Número de vèrtiços

𝑻_𝒅𝒎: Complexitat d'extraure mínim

Vore també

Referències

↑ Frana, Phil. “An Interview with Edsger W. Dijkstra”. Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249.
↑ (1959).Numerische Mathematik.1
269–271.doi:10.1007/BF01386390.
↑ “A Generalization of Dijkstra's Algorithm” (1977). Information Processing Letters 6: 1–5. doi:10.1016/0020-0190(77)90002-3.

Referències

Este artícul conté una traducció derivada de «Algoritmo de Dijkstra» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Dijkstra_Interview-1] Frana, Phil. “An Interview with Edsger W. Dijkstra”. Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249.

[Dijkstra1959-2] (1959).Numerische Mathematik.1
269–271.doi:10.1007/BF01386390.

[3] “A Generalization of Dijkstra's Algorithm” (1977). Information Processing Letters 6: 1–5. doi:10.1016/0020-0190(77)90002-3.

[1]

[2]

[3]