Algoritmi sui grafi

• Ordinamento topologico

• Cammino minimo dalla sorgente

Ordinamento topologicoDato un grafo finito orientato aciclico G = V, A, un ordinamento topologico di G consiste in una permutazione v1,…,vn di V tale che:

(vi, vj) A i j.

Esempio:

1 2

3 4

1, 3, 2, 4 è un ordinamento

topologico di G;

1, 2, 4, 3 non lo è perché (3,2) A

mentre 3 segue 2 in questa

permutazione.

G

Visita in profondità rivistaDFS (G = V,A)

foreach v V // inizializza i colori

Color[v] := White; Time[v] := indef;

time := 0; // variabile globale

foreach u V // itera la visita in prof.

if Color[u] = White then DFS-Visit(u)

DFS-Visit (u)

Color[u] := Gray; time := time + 1;

foreach v Adj[u]

if Color[v] = White then DFS-Visit(v);

Color[u] := Black;

Time[u] := time; time := time + 1;

Tempi e precedenzeTeorema. Sia G = V, A un grafo orientato aciclico.

Se (u,v) A, con u v, allora dopo DFS(G) Time[u] > Time[v].

Dim. P.a. sia (u,v) A tale che Time[u] < Time[v].

Allora al tempo t = Time[u] si ha

Color[u] = Black, Color[v] = White Color[v] = Gray.

• Color[v] = White è impossibile perché, se (u,v) A allora la visita di u non è completa (e quindi u non avrebbe potuto diventare nero al tempo t);

• Color[v] = Gray: allora esiste t< t tale che si abbia:

al tempo t Color[u] = White Color[v] = Gray,

al tempo t + 1 Color[u] = Color[v] = Gray.

Quindi esiste in G un cammino da v ad u (per la struttura della frontiera in DFS-Visit); ma allora (u,v) A implica che G sia ciclico.

Topological Sorting (TS)TS (Graph G = (V,A))

foreach v V // inizializza i colori

Color[v] := White;

l := NIL; // lista di vertici (globale)

foreach u V // itera la visita in prof.

if Color[u] = White then DFS-Visit-List(u)

return l;

DFS-Visit-List (Vertex u)

Color[u] := Gray;

foreach v Adj[u]

if Color[v] = White then DFS-Visit(v);

Color[u] := Black;

l := Cons(u,l); // se u precede v in l allora

// Time[u] > Time[v] in DFS(G)

Cammini minimiDato un grafo orientato pesato G = V, A, w (w:A funzione peso), ed un cammino = (v0, v1), … , (vk-1, vk) in G (not. v0 vk), si definisce il peso di come la somma dei pesi degli archi:

),()(*1 1 vvww i

k

i i

Problema del cammino minimo da sorgente singola.

Dato G orientato e pesato ed un vertice s, per ogni vertice v determinare un cammino tale che s v e w*() = (s,v), dove:

altrimenti

esiste se }|)(*min{),(

vuwvu

Nolta: w*() = 0 ( è il cammino vuoto), dunque (v,v) = 0 per ogni v.

Algoritmo di DijkstraE’ una tecnica greedy basata sulla definizione di un confine superiore d[v] a (s,v) per ogni v, che viene progressivamente migliorato.

Dijkstra(Graph G = (V,A), Vertex s)

foreach v V do d[v] := ;

d[s] := 0; q := EmptyPriorityQueue ();

// la priorita’ di ogni v in q e’ d[v]

foreach v V do Enqueue(v,q);

while not IsEmptyQueue(q) do

u := DequeueMin(q);

foreach v Adj[u] do

if d[v] > d[u] + w(u,v) then

d[v] := d[u] + w(u,v);

RedefinePrior(v,d[v],q);

return d;

rilassamento

coda con estrazione del minimo

assegna priorità d[v] al vertce v in q

OsservazioniNell’algoritmo di Dijkstra:

• si presuppone che il grafo abbia pesi non negativi oppure che sia aciclico;

• si mantiene una partizione tra vertici visitati e non (v è stato visitato se

e solo se d[v] );

• la priorità di un vertice v in q è d[v] ;

• l’invariante del ciclo principale è:

se v è stato visitato, allora d[v] = (s,v)

dove (s,v) è il valore di (s,v) nel sottografo formato dai vertici visitati e

dagli archi i cui estremi siano stati visitati.

Fine