Analisi e implementazione dell’algoritmo di

Dijkstra (Parte 1)

Algoritmicamente

August 1, 2009

http://algoritmicamente.wordpress.com/

1 Concetti fondamentali

Definizione 1 Un grafo e un insieme di vertici piu un insieme di archiche connettono coppie di vertici distinti.

Una definzione piu formale e comunque necessaria in quanto all’interno di talearticolo essa sara spesso utilizzata:

Definizione 1.1 Si dice grafo G una coppia ordina G=(V,E) di insiemi,dove V e l’insieme dei vertici ed E l’insieme degli archi .

Definizione 1.2 Un vertice e un punto terminale oppure un punto diintersezione di un grafo.

Definizione 1.3 Un arco e una connessione tra due vertici. Esso vieneindicato con la coppia ( i,j), dove i indica il vertice da cui parte l’arco (testa) ej indica il vertice in cui arriva (coda).

Per dare un’idea piu concreta di un grafo, viene mostrato un esempio di esso:

1

Come si puo notare l’insieme dei vertici V = {v1, v2, v3, v4, v5, v6} mentre l’insiemedegli archi e dato da tutte le coppie di vertici che vengono connessi tra loro, inquesto caso:G = {{v1, v2} , {v1, v4} , {v1, v6} , {v3, v6} , {v5, v2} , {v5, v6} , {v2, v4} , {v4, v6} , {v5, v6}}.Spesso (come nel caso trattato) ad ogni vertice o ad ogni arco viene associatoun peso ossia un valore numerico che indica la distanza che intercorre da duevertici. Tale tipo di grafo prende il nome di grafo pesato del quale viene datauna definizione piu formale.

Definizione 1.4 Un grafo pesato G e definito come una terna G = (V,E,P).Dove V ed E indicano il grafo G’ = (V,E) e P indica una generica funzioneche ad ogni vertice o ad ogni arco associa un valore numerico n ǫ [−∞, +∞].

Definizione 1.5 Un cammino (p) in un grafo e una sequenza di verticinei quali ogni vertice successivo e adiacente al precedente nel cammino.

Definizione 1.5.1 Un cammino semplice, e un cammino dove tutti ivertici sono distinti.

Definizione 1.5.2 Un ciclo e un cammino semplice, eccetto che il verticeiniziale e finale rimangono invariati.

fig. 2 Grafo pesato fig. 3 Possibile cammino di un grafo

Nella figura 3 e possibile vedere il cammino p = {v1, v2, v5, v3, v6}

2 Cammini minimi

L’analisi dei cammini minimi e il cuore di tale articolo, infatti l’algorito di Dijk-stra ha come scopo quello di trovare il cammino minimo all’interno di un grafo.Prima di tutto bisogna far chiarimento su cosa sia un cammino minimo

Definizione 2 Dato un grafo G=(V,E,P) ed un cammino p = {v1, v2, ..., vn}il peso di un cammino ω(p) e la somma dei pesi degli archi che compongonotale cammino.

2

Dalla figura risulta che il peso del cammino in rosso e dato da:ω(p) = (1 + 5 + 21 + 3) = 30.

Detto cio e possibile ora definire il cammino minimo di un generico grafo G.

Definizione 2.1 Dato un grafo G = (V,E,P) il cammino minimo di talegrafo e il piu piccolo dei ω(pn), dove pi 1 ≤ i ≤ n e un generico cammino delgrafo G.

Grazie a tale definizione appare piu chiaro lo scopo dell’algoritmo di Dijkstra,infatti mediante esso possiamo trovare IL cammino minimo all’interno di ungrafo pesato G.Seguono dunque alcuni esempi per mostrare il cammino minimo all’interno diun grafo:

fig. 4 Cammino minimo corretto fig. 5 Cammino minimo scorretto

Come si puo dunque notare dalle due figure, il cammino minimo (per arrivaredal vertice 1 al vertice 3) non e quello “piu breve” cioe quello che percorre menoarchi, ma, come detto nella definizione, e quello la cui somma dei pesi degli archie minima.Tale problema non e banale in quanto vi e un’importante osservazione da fare:Come si puo notare in entrambe le figure (fig.4, fig5) il cammino minimo noninizia affatto con l’arco di peso minore, anzi, in questo caso il cammino minimoe quello che ha come arco di partenza, quello con il peso maggiore (gli altri sonoE1 = {v1, v6} il quale ha peso 2, e E2 = {v1, v4} il quale ha peso 1). Cio ci da ladimostrazione che il cammino minimo e dato da una somma, e in quanto sommasi deve tener conto degli addendi che la compongono (in questo caso i pesi). In-oltre, dalla definizione 1.4 si evince che i pesi possono anche essere negativi,dunque per quanto possa essere grande il peso del primo arco di un percorso, ilpeso di un cammino potra essere “diminuito” a causa di un cammino di valorenegativo.

3

3 Algoritmo di Dijkstra

L’algoritmo di Dijkstra permette di poter calcolare i cammini minimi all’internodi un grafo, la forza di tale algoritmo e la semplicita del codice e soprattuttola sua efficienza, infatti la complessita nel caso peggiore di tale algoritmo e :O(|E|+|V|log |V |) .Esso possiede inoltre delle proprieta particolari :

Proprieta 3 L’algoritmo di Dijkstra risolve i problemi di cammino min-imo,da un vertice di partenza ad un vertice di arrivo, nei grafi che non hannopesi negativi.

Proprieta 3.1 Con L’algoritmo di Dijkstra possiano trovare ogni SPT inuna grafo denso in un tempo lineare.

La proprieta 3.1 viene data solo a scopo informativo, non e interesse di talearticolo trattare argomenti non inerenti con l’analisi di tale algoritmo, mentrela proprieta 3 puo essere dimostrata, tale dimostrazione verra trattata in se-guito.Il funzionamento e molto semplice, dato un grafo e un vertice di partenza,l’algoritmo mostra tutti i cammini minimi per raggiungere gli altri nodi, perpoter meglio comprendere tale algoritmo viene mostrato inizialmente il suo pseu-docodice completo.

function Dijkstra(Graph, source):for each vertex v in Graph:

dist[v ] := infinityprevious[v ] := undefined

dist[source] := 0Q := the set of all nodes in Graphwhile Q is not empty:u := vertex in Q with smallest dist[] 8if dist[u] = infinity:9break 10

remove u from Q 11for each neighbor v of u: 12alt := dist[u] + dist between(u, v) 13if alt < dist[v ]: 14dist[v ] := alt 15previous[v ] := u 16

return previous

La I riga non e altro che il prototipo della funzione, la quale (come gia detto)accetta in input un grafo e un vertice sorgente.Possiamo dividere tale algoritmo in due parti, l’inizializzazione del grafo datoin input, e l’algoritmo vero e proprio.

4

Per quanto riguarda l’inizializzazione, essa e effettuata dalle righe 2,3,4,5,6 nellequali vengono effettuate le inizializzazioni per tutti i nodi, piu nello specifico,le righe 3,4 settano le distanze dal vertice sorgente agli altri nodi a ∞, la riga5 setta la distanza del vertice sorgente a 0, e infine la riga 6 crea l’insieme Q ilquale contiene tutti i nodi del grafo dato in input. Per chiarire meglio quantomostriamo un esempio.

fig. 6 Grafo dato in input fig. 7 Grafo inzializzato

L’esempio mostrato accetta in input il grafo di fig. 6 e si prende come ver-tice sorgente v1. Le righe 3,4, come gia detto, settano le distanze di tutti ivertici al vertice sorgente ad ∞, tale distanza viene indicata ponendo vicino alvertice interessato il suo valore, mentre la riga 5 setta la distanza del verticesorgente a 0. Infine vi e la riga 6, la quale crea l’insieme di tutti i vertici delgrafo Q, nel caso dai noi analizzato, al momento dell’inizializzazione, l’insiemeQ = {v1, v2, v3, v4, v5, v6}.La seconda parte dell’algoritmo analizza il grafo per estrarne i cammini minimi,essa va dalla riga 7 alla riga 16.Possiamo subito notare che essa e composta da un ciclo principale (while Q is

not empty:) dal quale poi si diramano gli altri cicli, tale ciclo termina ovvia-mente quanto l’insieme Q e vuoto.La riga 8 prende dall’insieme Q il vertice che ha distanza minore, poiche tuttii vertici eccetto v1 hanno distanza infinita, verra selezionato v1 dall’insieme Q.La riga 9 consiste in un if, il quale in tal caso non verra preso in considerazionein quanto dist[v1] = 0 6= ∞. La riga 11 eliminera in vertice v1 dall’insieme Qil quale ora diventera Q = {v2, v3, v4, v5, v6}. La riga 12 da origine ad un altrociclo, il quale analizza i pesi degli archi che connettono i vertici, tale ciclo prendein analisi tutti i vertici che sono collegati direttamente a v1 e ne analizza il pesodegli archi che li uniscono, viene quindi preso in considerazione v2 il quale hauna distanza (peso dell’arco) 3 con v1, a tal proposito nella riga 13 viene creatauna variabile temporale alt la quale sommera il peso dell’arco che unisce i verticicon la distanza del vertice preso in considerazione poiche la distanza {v1v,2 } =3, e poiche v1 ha in origine distanza = 0, alt = 0 + 3 = 3. Una volta calcolatatale distanza, se tale distanza e minore di quella presente nel vertice vicino a

5

v1(riga 14) cioe la distanza di v2 allora il vertice v2 assume distanza uguale adalt (riga 15), dunque poiche alt < v2 = ∞, allora v2 = alt = 3, nella riga 16viene creato un array nel quale viene aggiunto il vertice v2 e cosı via per gli altrivertici vicino ad v. Per chiarire le idee viene dato un esempio pratico di quantodetto.

fig. 8 v1 viene preso dall’insieme Q fig. 9 uno dei “vicini” di v1 viene selezionato

Viene selezionato v1 perche dell’insieme Q esso e quello che ha come distanzaminore (8) e viene tolto dall’insieme Q (11), viene poi selezionato un vicino div1 (12), in questo caso v2, e poiche 0+3 = 3 < ∞ (13,14), la sua distanza vieneposta uguale a 3 (15), viene aggiunto v2 all’array previous. Poiche v1 ha ancoraaltri “vicini”, vengono selezionati anch’essi nel for dunque avremo:

fig. 10 Completamente del ciclo for

Anche gli altri vertici vicini a v1 vengono selezionati e viene calcolata la distanzamediante l’analisi dei pesi degli archi che li uniscono.Una volta effettuata tale operazione, il processo inizia nuovamente, il ciclo while

6

esegue un’altra iterazione e si passa alla linea 8, la quale scegliera il vertice conla distanza piu piccolo all’interno dell’insieme Q, e da ricordare che la linea 11aveva modificato il contenuto di Q, dunque ora verra selezionato come verticeda analizzare, v4, poiche esso ha la distanza minore tra tutti i vertici di Q. Lelinee 9,10 anche in questo caso non vengono prese in cosiderazione poiche v4

= 1 6= ∞, dunque la linea 11 eliminera l’elemento v4 dall’insieme Q, il qualeora risulta essere composto da Q = {v2, v3, v5, v6}. Una volta effettuata taleoperazione si entra nel ciclo for, il quale andra ad analizzare (come gia vistoper v1) tutti i vertici ad esso collegati, nell’esempio mostrato l’unico ad esserevicino a v4 e v6, la riga 13 crea la variabile alt = 1 + 13 = 14, la riga 14 indicache se la distanza di v6 > alt allora tale distanza deve essere sovrascritta conil valore di alt, dunque poiche 30 > 14 ne segue che il valore delle distanza div6, viene settato a 14 (riga 15), infine la riga 16 aggiunge all’array il vertice v4,il quale contera ora previous[] = {v1, v4}, viene mostrato graficamente quantodescritto.

fig. 11 v4 e il vertice con distanza minore fig. 12 viene calcolata la distanza di v6

Come si puo notare dalla fig. 11 tra tutti i vertici, v4 e quello con distanzaminore, e poiche esso ha come unico vicino v6, verra calcolata la sua distanzabasandosi sul peso dell’arco che li unisce, poiche tale distanza e uguale a 14,mentre la distanza precedente e uguale a 30, tale distanza viene aggiornatamettendo il valore minore dei due.Tale processo continua per tutti i vertici rimanenti fino a quando essi non ver-ranno esaminati tutti, cioe quando l’insieme Q che contiene tutti i vertici e vuoloQ = {φ}. Alla fine di tale processo il grafo apparira come in figura.

7

fig. 13 fine dell’algoritmo con le distanza minime

8