Cammini minimi con una
sorgente
Problema dei cammini minimi
Varianti e archi negativi
Sottostruttura ottima di un cammino minimo
Algoritmo di Dijkstra
Complessità dell’algoritmo
Rappresentazione dei cammini minimi
Problema dei cammini minimi
Input: un grafo G=(V,E) orientato e pesato, con una
funzione peso w: E → R, che associa ad ogni arco in E
un peso a valore nei reali.
1
9
8
1
2
1
3
1
1
3
1
1
6
4
4
-3
5
6
1
1
4
-1
1
3
3
6
2
1
5
1
Problema dei cammini minimi
Il peso di un cammino p= <v1, v2, …,vk> è la somma
dei pesi degli archi che lo costituiscono.
k
w(p)   w(v i 1 , v i )
i2
15 min + 50 min = 65 min
50
MC
20
p1= <PO, FI, SI> =
PT
LU
20
35
25
20
PO
PI
FI
LI
35
50
65
SI
70
GR
p2 = <PO, FI, AR, SI> =
15
60
40
AR
15 min + 35 min + 40 min =
= 90 min
p3 = <PO, FI, PI, LI, GR,
SI> = 160 min
Problema dei cammini minimi
Il peso di un cammino minimo dal vertice u al vertice
v è definito da:


p
min w(p) : u 

v se esiste un cammino da u a v
δ(u, v)  

altrimenti

Un cammino minimo dal vertice u al vertice v è definito
come un qualunque cammino p con peso w(p) = δ(u,v).
Può non essere unico!
δ(6,1) = 7
9
8
1
2
1
3
3
3
3
3
4
-2
5
6
-1
p1 = <6, 2, 3, 1 >
w(p1) = 7
p2 = <6, 1>
w(p2) = 9
p3 = <6, 5, 6, 2, 3, 1 >
w(p3) = 9
p4 = <6, 5, 4, 3, 1 >
w(p4) = 7
Vari problemi
• Problema di cammini minimi con sorgente singola: si
vuole trovare un cammino minimo da un dato vertice
sorgente s ad ogni vertice v in V.
• Problema di cammini minimi con destinazione
singola: si vuole trovare da ogni vertice v in V un
cammino minimo ad un dato vertice destinazione t.
• Problema di cammini minimi tra una coppia: si vuole
trovare un cammino minimo da u a v.
• Problema di cammini minimi tra tutte le coppie:
determinazione di un cammino minimo per ogni coppia di
vertici u e v.
Archi con pesi negativi
Un possibile problema può essere rappresentato dalla
presenza di pesi negativi sugli archi e di cicli che
contengano archi con pesi negativi.
Se il peso di un ciclo è negativo, allora tutti i nodi
raggiungibile dal ciclo hanno un cammino minimo
infinitamente negativo (-∞).
Ciclo <6,5> negativo.
9
8
1
1
3
Ogni volta che compio un giro
diminuisco il peso del cammino
che passa per il ciclo.
2
3
3
3
3
4
-2
5
6
-7
δ(6,1) = -∞
Sottostruttura ottima di un cammino
minimo
Sottocammini di cammini minimi sono cammini minimi
Dato un grafo G=(V,E) con funzione peso w:E→ R, sia
p= <v1, v2, …,vk> un cammino minimo da v1 a vk. Per ogni
i e j tali che 1 ≤ i ≤ j ≤ k, ha che il sottocammino
pij= <vi, vi+1, …,vj> è un cammino minimo.
w(pij)=δ(i,j)
1
i
j
k
p’ij
Dato un altro sottocammino da i a j p’ij, necessariamente
w(pij ) ≤ w(p’ij), altrimenti il cammino minimo passa per p’ij.
Sottostruttura ottima di un cammino
minimo
Di conseguenza:
Si supponga che un cammino minimo p da una sorgente
ad un vertice v passi per l’arco (u,v) con peso w(u,v). Il peso
del cammino minino da s a v è δ(s,v) = δ(s,u) + w(u,v).
δ(s,u)
i
cammino minimo tra u e v
u
w(u,v)
v
δ(s,v) = δ(s,u) + w(u,v).
Più in generale, se esiste un arco (u,v), allora si ha:
δ(s,v) ≤ δ(s,u) + w(u,v).
Algoritmo di Dijkstra
L’algoritmo di Dijkstra risolve il problema dei cammini
minimi con sorgente singola su un grafo orientato e
pesato G=(V,E) nel caso in cui tutti i pesi degli archi siano
non negativi.
Ci sono due insiemi:
• S: dove d[v] = δ(s,v), quindi un cammino minimo tra s e v
è stato determinato.
• Q = V-S: una coda a priorità dove d[v] ha il valore del
cammino con peso minore finora scoperto.
All’inizio, S contiene solo s, d[s]=0, mentre Q=V-{s} con
d[v]=∞.
Algoritmo di Dijkstra
DIJKSTRA(G,w,s)
1.
for ogni vertice u in V[G]
// inizializzazione di ogni vertice
2.
do d[u] ← ∞
3.
p[u] ← NIL
4.
d[s] ← 0
// si comincia dal vertice s
5.
Q ← V[G]
// coda a priorità
6.
S←Ø
// insiemi dei cammini minimi trovati
7.
while Q≠Ø
// termina quando la coda Q è vuota
8.
do u ← EXTRACT-MIN(Q)
// prendi il cammino in Q più
piccolo
9.
S ← S U {u}
// inserisci u in S
10.
for ogni vertice v in Adj[u] // aggiorna cammini minimi in Q
con v adiacente a u
11.
do if d[v] > d[u] + w(u,v)
12.
then d[v] ← d[u] + w[u,w]
13.
p[v] ← u
Esempio
u
10
3
s
0
∞
2
v
1
∞
3
s
9
u
10
4 6
0
10
2
v
1
∞
x
5
5
y
x
(a)
3
s
0
v
1
8
2
5
x
3
s
4 6
(d)
5
5
y
u
10
13
9
2
2
9
4 6
x
0
2
y
5
5
9
3
s
9
4 6
x
2
(e)
y
u
10
0
v
1
8
2
9
9
4 6
7
7
7
7
2
(c)
v
1
8
14
7
∞
2
7
5
1
8
(b)
u
10
0
v
7
∞
2
3
s
4 6
7
5
∞
9
u
10
7
y
5
5
x
2
(f)
7
y
Correttezza algoritmo
Se si esegue un l’algoritmo di Dijkstra su un grafo orientato
e pesato G=(V,E) nel caso in cui tutti i pesi degli archi siano
non negativi, allora al termine vale d[v] = δ(s,v) per ogni v
in V.
Dimostrazione
Supponiamo per assurdo che u sia il primo vertice ad
entrare in S tale che d[u] ≠ δ(s,u). Prendiamo un cammino
minimo da s a u, che può essere decomposto in
s→x→y→u, con x in S, y in Q e (x,y) arco di G.
s
S
p1
x
Può essere
y
p2
u
s=xoy=u
Correttezza algoritmo
s
S
p1
d[x] = δ(s,x)
x
y
p2
u
x è entrato prima
di u in S.
Si ha anche d[y] = δ(s,y) = δ(s,y) + w(x,y), perché
sottocamino di un cammino minimo.
Inoltre d[y] = δ(s,y) ≤ δ(s,u) ≤ d[u].
Nell’algoritmo u viene scelto prima di y (EXTRACT-MIN(Q)), quindi
deve valere l’uguaglianza:
d[y] = δ(s,y) = δ(s,u) = d[u].
ASSURDO! δ(s,u) ≠ d[u].
Complessità
Analisi del tempo di esecuzione:
• Si consideri che la coda con priorità Q come un array
lineare.
• EXTRACT-MIN(Q): ricerca del minimo in Q. Bisogna
vedere tutti i valori in Q, richiede tempo O(|V|)
• EXTRACT-MIN(Q) viene eseguito per ogni vertice quindi il
tempo totale è O(|V|x|V|) = O(|V|2)
• Come in BFS vengono, si esamina la lista di adiacenza
di ogni vertice v, che entra solo una volta in S.
• La somma di tutte liste di adiacenze è |E|.
• Il tempo totale dell’algoritmo di Dijkstra è O(|E|+|V|2).
Rappresentazione dei cammini
minimi
Come nella visita in ampiezza (BFS), l’algoritmo Dijkstra
definisce un sottografo dei predecessori Tp=(Vp,Ep).
L’albero che ne segue contiene i cammini minimi individuati
da s ad ogni vertice raggiungibile v.
Nota: questo vale solo al termine dell’algoritmo.
u
10
3
s
0
1
8
2
u
v
9
3
s
9
4 6
v
1
8
9
Tp=(Vp,Ep)
0
7
5
5
x
2
7
y
5
5
x
2
7
y