Grafi: Algoritmo di Dijkstra

Dati e Algoritmi 1: A. Pietracaprina

Grafi

Cammini minimi su grafi pesati

• V `e l’insieme dei vertici; • E `e l’insieme degli archi:

• w : E → < funzione che associa un peso reale a ciascun arco. Esempio (da [GTG14]):

Cammini minimi su grafi pesati

Si ricordi che:

• Lalunghezza di un cammino u1, u2, . . . , uk `e la somma dei pesi degli

archi del cammino, ovvero

k−1

X

i =1

w (ui, ui +1).

Oss.: Sew (e) = 1per ognie ∈ E, la lunghezza di un cammino `e pari al numero di archi (come in un grafo non pesato).

• La distanza d (u, v )tra i due verticiu, v ∈ V `e laminima lunghezza di un cammino da u a v, e il cammino che la realizza si chiama cammino minimo da u a v

Cammini minimi su grafi pesati

Proposizione

Seu1, u2, . . . , uk `e un cammino minimo dau1a uk, alloraui, ui +1, . . . , uj

Cammini minimi su grafi pesati

Come calcoliamodistanzeecammini minimi in un grafo pesato?

Definizione

Dato un grafo pesatoG = (V , E , w ), semplice e non diretto, e un vertice s ∈ V, il problema deiSingle-Source Shortest Paths (SSSP)richiede di determinaretutte le distanze tra s e gli altri vertici di V e i relativi cammini minimi(opportunamente rappresentati).

Ipotesi: Assumiamo cheG non contenga cicli di peso negativo,

altrimenti per coppie di vertici nella stessa componente connessa del ciclo esisterebbero cammini di lunghezza negativa arbitrariamente piccola. Osservazione: Sew (e) = 1per ognie ∈ E, la BFS risolve il problema dei SSSP in tempoΘ (n + m)(doven = |V |em = |E |).

Algoritmo di Dijkstra per SSSP

• Generalizza lo schema della BFS al caso pesato. A partire da un verticesorgente s ∈ V:

• Esegue una serie di iterazioni che fanno crescere progressivamente lacloud di vertici le cui distanze da s e i relativi cammini minimi sono stati identificati;

• Lacloud `e inizializzata con {s};

• Per ogniv ∈ V mantiene la distanza corrente di v da s, relativa a cammini interni alla cloud (tranne, eventualmentev);

• In ciascuna iterazione vieneaggiunto alla cloud il vertice esterno alla cloud pi`u vicino a s;

• Ivertici esterni alla cloud sono mantenuti in una Priority Queuein base alla loro distanza das.

Dettagli implementativi

Per ogni verticev ∈ V usiamo i seguenti campi:

• v .D: memorizza la distanza corrente da s (D[v] in [GTG14]); • _{v .parent}: memorizza il predecessore div nel cammino minimo

corrente das av.

Supponiamo che il verticeuvenga aggiunto alla cloud. La seguente operazione (edge relaxation) serve per aggiornare la distanza corrente da sdi un vicinov di u:

Algoritmo di Dijkstra: pseudocodice

Input: grafo non direttoG = (V , E , w )con pesi non negativi sugli archi, e sorgentes ∈ V

Output: distanze e cammini minimi das per ogniv ∈ V, rappresentati dai campiv .Dev .parent

s.D ← 0;s.parent ←null; forallv ∈ V − {s} do

v .D ← +∞; v .parent ←null

Q ←Priority Queue con tutti i verticiv ∈ V (chiavev .D); while (Q is not empy) do

u ← Q.removeMin();

forall ((u, v ) ∈ E withv ∈ Q) do if (u.D + w (u, v ) < v .D) then

v .D ← u.D + w (u, v ); v .parent ← u;

Correttezza di ShortestPaths

La correttezza dell’algoritmo `e una conseguenza immediata dei seguenti lemmi.

SiaG = (V , E , w )un grafo non diretto con pesi non negativi sugli archi e sias ∈ V un vertice arbitrario.

Lemma 1

Alla fine di ciascuna iterazione del ciclo while di ShortestPaths(G , s), per ogniv ∈ V si ha che

• Sev .D = +∞, allorav .parent = null.

• Sev .D < +∞, il cammino ottenutorisalendo da v di “parent in parent”`e un cammino das av di lunghezzav .D.

Lemma 2

Durante l’esecuzione di ShortestPaths(G , s), quando un verticeu`e estratto daQ, il campou.D`e uguale alla distanza d (s, u)di udas.

Complessit`

a di ShortestPaths

La complessit`a di ShortestPaths dipende dalla implementazione scelta per la Priority QueueQ.

Consideriamo due possibili implementazioni: HeapeDoubly-linked list non ordinata.

Osservazioni:

• Unaentry di Q associata a un vertice v ha v .D come chiave e un puntatore all’oggetto che rappresenta v come valore.

• Si assume che nella rappresentazione dei vertici,l’oggetto che rappresenta un vertice v mantenga un puntatore alla entry corrispondente di Q (il puntatore sar`a null sev 6=∈ Q).

Complessit`

a di ShortestPaths

Lemma

Se il grafoG = (V , E , w )hanvertici, le complessit`a delle operazioni su Q previste da ShortestPaths(G , s)sono le seguenti:

Operazione Heap Doubly-Linked List

Costruzione iniziale Θ (n) Θ (n)

removeMin Θ (log n) Θ (n)

Aggiornamento chiave Θ (log n) Θ (1)

La prova del lemma si basa sulle seguenti osservazioni:

• Aggiornamento di una chiave (caso Heap): l’aggiornamento pu`o creare unaviolazione della heap-order propertyrispetto alla entry nel padre o alle entry nei figli. Tale violazione pu`o essere sanata con un up-heap bubblingo undown-heap bubbling in tempo

Complessit`

a di ShortestPaths

Teorema

SiaG = (V , E , w )un grafo non diretto connvertici edmarchi e con pesi non negativi sugli archi. Per ognis ∈ V la complessit`a di

ShortestPaths(G , s)`eO min{n2_{, (n + m) log n}}
.

Ottimizzazione

Lacomplessit`a di ShortestPaths pu`o essere migliorataimplementando laPriority Queue Q tramite un Fibonacci Heap, che `e una lista di Heap tramite la quale gliO (m)aggiornamenti di chiave previsti dall’algoritmo richiedono, complessivamenteO (m)operazioni.

Teorema (senza prova)

SiaG = (V , E , w )un grafo non diretto connvertici edmarchi e con pesi non negativi sugli archi. Utilizzando unFibonacci Heapper implementare la Priority QueueQ, la complessit`a di

Esercizio

SiaG = (V , E , w )un grafo non diretto connvertici edmarchi e con pesi non negativi sugli archi.

1 Progettare una modifica di ShortestPaths(G , s)in modo che la complessit`a siaO (n + (ns + ms) log ns), dovens `e il numero di

vertici e ms il numero di archi nella componente connessa dis (Cs).

2 Dire se l’algoritmo modificato restituisce comunque le distanze corrette anche per i vertici non inCs.

Riepilogo sui Grafi

• Concetti fondamentali: cammino, ciclo, grafo connesso, subgraph, spanning subgraph, alberi radicati/liberi, spanning tree/forest. • Relazione tra la somma dei degree e il numero di archi in un grafo. • Relazioni tra numero di vertici e numero di archi in alberi, foreste e

grafi connessi. • Depth-First Search:

• Pseudocodice. • _{Analisi e propriet`a.}

• Problemi computazionali risolvibili tramite DFS. • Breadth-First Search:

Riepilogo sui Grafi

• Cammini minimi su grafi pesati e loro propriet`a. • Problema SSSP.

• Algoritmo di Dijkstra: • Pseudocodice. • Correttezza. • Complessit`a.