Cammini minimi

Tra le proprietà di un cammino $p=(n_0,...,n_k)$ è definita la lunghezza: $$w(p)=\sum _{i=1}^{k}w(n_{i-1},n_i)$$ l'insieme di cammini $\mathcal{C}(u,v)$, che contiene tutti i cammini da $u$ a $v$, e la distanza: $$\delta (u,v)=\{\begin{array}{ll}\underset{p\in \mathcal{C}(u,v)}{\min }w(p)& \text{se }\mathcal{C}(u,v)\ne \varnothing \\ \infty & \text{se }\mathcal{C}(u,v)=\varnothing \end{array}$$ che diventerebbe $-\infty$ se ci fosse un ciclo negativo, perchè allora esisterebbe sempre un $w(p)$ minore.

Per esempio, il cammino da $s$ a $c$ possiede un ciclo negativo e quindi $\delta (s,c)=-\infty$:

Struttura

Gli algoritmi principali, come per quello di Prim, memorizzano due campi per ogni vertice $u\in V$:

• La stima della distanza minima d[u], che alla fine dovrà essere uguale a $\delta (s,u)$
• Il predecessore 𝜋[u], da cui è partito l'arco verso $u$ che porta al peso finale d[u]

Inoltre, gli algoritmi fanno uso delle funzioni ausiliarie:

• Init Single Source

  init_ss(G, s)
    for each u in G.V
      d[u] = +Infinity
      𝜋[u] = NIL
    d[s] = 0
    return d, 𝜋
  

  con costo $\Theta (1)$.

• Relax

  relax(u, v, w, d, 𝜋)
    if d[v] > d[u] + w(u, v)
      d[v] = d[u] + w(u, v)
      𝜋[v] = u
  

  che diventa $O(\log n)$ per l'assegnamento a d[v], se d è usato in una coda di priorità.

Proprietà

Sia sui grafi orientati che non orientati valgono le proprietà:

• Grafo dei predecessori

  Il grafo $G_{\pi }=(V_{\pi },E_{\pi })$ è detto dei predecessori se dipende da $\pi$, ovvero se è costruito tale che: $$\begin{array}{rl}{V}_{\pi }& =\{s\}\cup \left\{u\in V|\exists {\pi }_u\right\}\\ E_{\pi }& =\left\{({\pi }_u,u)\in E|u\in V_{\pi }\setminus \{s\}\right\}\end{array}$$ ovvero un'istanza dello stato dell'algoritmo, che alla fine diventerà l'albero dei cammini minimi.

• Albero dei cammini minimi

  Il sottografo $G^{\prime }=(V^{\prime },E^{\prime })$ del grafo $G$ rappresenta i cammini minimi quando:

  • $V^{\prime }=\left\{u\in V|\delta (s,u)\ne \infty \right\}$, ovvero l'insieme dei nodi raggiungibili in $G$ da $s$
  • $G^{\prime }$ forma un albero con radice $s$
  • Il cammino tra $s$ e qualsiasi $u$ in $G^{\prime }$ è minimo in $G$

• Proprietà dei sottocammini minimi

  Ogni sottocammino del cammino minimo $p$ è anch'esso minimo, perchè altrimenti $p$ non lo sarebbe.

• Disuguaglianza triangolare

  Dato $G=(V,E)$ ed un arco $(u,v)\in E$, allora: $$\delta (s,v)\le \delta (s,u)+w(u,v)$$

  Che è dimostrato perchè nel caso di

  • $\delta (s,u)=\infty$ allora $\delta (s,v)\le \infty$
  • $\delta (s,u)=-\infty$ allora è presente il ciclo negativo anche tra $s$ e $v$, quindi $\delta (s,v)=-\infty$
  • $\delta (s,u)\in \mathbb{R}$ allora, sia che $(u,v)$ sia il migliore o peggiore tra gli archi entranti di $v$, è verificata

• Proprietà del limite inferiore

  Su qualsiasi algoritmo che usa init_ss e che modifica $d$ e $\pi$ solamente con relax vale che: $$\delta (s,v)\le d_v,\forall v\in V$$

  Inoltre, se ad un certo punto $d_v=\delta (s,v)$, ulteriori chiamate a relax non cambieranno più $d$.

  La dimostrazione si concentra sui principali momenti che coinvolgono $d$:

  • Dopo init_ss, se:

    • $v\ne s$, allora $\delta (s,v)\le d_v=+\infty$
    • $v=s$, allora $\delta (s,s)\le d_s=0$ anche in presenza di cicli negativi, i.e. $\delta (s,s)=-\infty$

  • Dopo relax su $(u,v)$, supponendo per assurdo che causi per la prima volta $d_v<\delta (s,v)$:

    Siccome la relax dev'essere entrata nell'if perchè le ipotesi siano vere, $$d_u+w(u,v)=d_v<\delta (s,v)\le \delta (s,u)+w(u,v)$$ per l'ipotesi e per la disuguaglianza triangolare, ovvero che $d_u<\delta (s,u)$ che è assurdo perchè $v$ non sarebbe il primo ad aver infranto la proprietà, ma lo sarebbe $u$.

• Proprietà della convergenza

  Dato $p=(s,...,u,v)$ minimo, se $d_u=\delta (s,u)$ allora dopo la prima relax su $(u,v)$: $$d_v=\delta (s,v)$$

  Questo è dimostrabile con il limite inferiore, e perchè dopo la relax si ha che $d_v\le d_u+w(u,v)$: $$\begin{array}{rl}\delta (s,v)\le d_v& \le d_u+w(u,v)\\ & =\delta (s,u)+w(u,v)\\ & =\delta (s,v)\end{array}$$