Dijkstra

L'algoritmo trova i cammini minimi da una singola sorgente $s$ a tutti i nodi di un grafo $G$ con pesi positivi, effettuando relax sui vicini dei nodi estratti con distanza minore, similarmente a quello di Prim:

dijkstra(G, w, s)
  d, 𝜋 = init_ss(G, s)
  Q = G.V
  while Q.heap_size > 0
    u = extract_min(Q)  // Sceglie in base a d
    for each v in neighbors(G, u)
      relax(u, v, w, d, 𝜋)
  return (d, 𝜋)

La complessità dipende da Q, infatti se $G$ è denso conviene usare un array perchè $m\approx n^2$: $$T(n,m)=\underset{\text{init\_ss}}{\underbrace{O(n)}}+n\cdot \underset{\text{extract\_min}}{\underbrace{O(n)}}+\underset{m}{\underbrace{\sum _{i=1}^n\text{out-deg}(i)}}\cdot \underset{\text{relax}}{\underbrace{O(1)}}=O(n^2)$$ altrimenti se $G$ è sparso conviene una coda di minima priorità perchè $m\approx n$: $$T(n,m)=\underset{\text{init\_ss}}{\underbrace{O(n)}}+n\cdot \underset{\text{extract\_min}}{\underbrace{O(\log n)}}+\sum _{i=1}^n\text{out-deg}(i)\cdot \underset{\text{relax}}{\underbrace{O(\log n)}}=O(m\log n)$$

Correttezza

L'algoritmo è corretto, perchè alla fine si ha che $\forall u\in V,d_u=\delta (s,u)$ e $G_{\pi }$ è un albero di cammini minimi.

Si può dimostrare la prima affermazione supponendo per assurdo che esista un $u\in V$ per cui $d_u\ne \delta (s,u)$ e che sia il primo nodo per cui capita. In particolare, attraverso le seguenti osservazioni:

1. $u\ne s$, perchè $\delta (s,s)\ne -\infty$ perchè non ci sono pesi negativi, quindi $d_s=\delta (s,s)=0$

2. All'estrazione di $u$ l'insieme $V\setminus Q\ne \varnothing$, perchè conterrà almeno $s$

3. Si può raggiungere $u$ da $s$, ovvero $\delta (s,u)\ne \infty$, perchè altrimenti $\delta (s,u)=\infty =d_u$ è contro l'ipotesi

4. Nello stato dell'algoritmo dopo l'estrazione di $s\in V\setminus Q$ e prima di $u\in Q$:

   Per il punto 3 esiste un $p=(s,...,u)$ minimo, e dato un $(x,y)$ in $p$ per cui $x\in V\setminus Q$ e $y\in Q$:

   1. $d_x=\delta (s,x)$ perchè $u$ è il primo per cui l'ipotesi assurda vale
   2. La relax su $(x,y)$ causa $d_y=\delta (s,x)+w(x,y)=\delta (s,y)$ per la convergenza
   3. Dato che si sta per estrarre $u$, allora $d_u\le d_y$ perchè anche $y\in Q$
   4. $\delta (s,y)\le \delta (s,u)$ perchè $(s,...,y)$ è sottocammino di $p$ e non ci sono pesi negativi
   5. $\delta (s,u)\le d_u$ per il limite inferiore

   Di conseguenza, con le osservazioni 4.5, 4.3, 4.2, 4.4 rispettivamente: $$\begin{array}{rl}\delta (s,u)\le d_u& \le d_y\\ & =\delta (s,y)\\ & \le \delta (s,u)\end{array}$$ ovvero che $\delta (s,u)\le d_u\le \delta (s,u)$ che però è assurdo, perchè va contro l'ipotesi.