Analisi e implementazione dellalgoritmo 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 allinterno di talearticolo essa sara` spesso utilizzata:

Definizione 1.1 Si dice grafo G una coppia ordina G=(V,E) di insiemi,dove V e` linsieme dei vertici ed E linsieme 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 larco (testa) ej indica il vertice in cui arriva (coda).

Per dare unidea piu` concreta di un grafo, viene mostrato un esempio di esso:

1

Come si puo` notare linsieme dei vertici V = {v1, v2, v3, v4, v5, v6}mentre linsiemedegli 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

Lanalisi dei cammini minimi e` il cuore di tale articolo, infatti lalgorito di Dijk-stra ha come scopo quello di trovare il cammino minimo allinterno 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 dellalgoritmo di Dijkstra,infatti mediante esso possiamo trovare IL cammino minimo allinterno di ungrafo pesato G.Seguono dunque alcuni esempi per mostrare il cammino minimo allinterno 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` unimportante osservazione da fare:Come si puo` notare in entrambe le figure (fig.4, fig5) il cammino minimo noninizia affatto con larco 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

Lalgoritmo di Dijkstra permette di poter calcolare i cammini minimi allinternodi 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 Lalgoritmo 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 Lalgoritmo 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 lanalisi 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,lalgoritmo 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, linizializzazione del grafo datoin input, e lalgoritmo vero e proprio.

4

Per quanto riguarda linizializzazione, 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 linsieme 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

Lesempio 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 linsieme di tutti i vertici delgrafo Q, nel caso dai noi analizzato, al momento dellinizializzazione, linsiemeQ = {v1, v2, v3, v4, v5, v6}.La seconda parte dellalgoritmo 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 isnot empty:) dal quale poi si diramano gli altri cicli, tale ciclo termina ovvia-mente quanto linsieme Q e` vuoto.La riga 8 prende dallinsieme Q il vertice che ha distanza minore, poiche tuttii vertici eccetto v1 hanno distanza infinita, verra` selezionato v1 dallinsieme 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 dallinsieme 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 dellarco) 3 con v1, a tal proposito nella riga 13 viene creatauna variabile temporale alt la quale sommera` il peso dellarco 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 dallinsieme Q fig. 9 uno dei vicini di v1 viene selezionato

Viene selezionato v1 perche` dellinsieme Q esso e` quello che ha come distanzaminore (8) e viene tolto dallinsieme 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 allarray previous. Poiche v1 ha ancoraaltri vicini, vengono selezionati anchessi nel for dunque avremo:

fig. 10 Completamente del ciclo for

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

6

esegue unaltra iterazione e si passa alla linea 8, la quale scegliera il vertice conla distanza piu` piccolo allinterno dellinsieme 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 lelemento v4 dallinsieme 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, nellesempio mostrato lunico 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 allarray 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 dellarco 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 linsieme Q che contiene tutti i vertici e` vuoloQ = {}. Alla fine di tale processo il grafo apparira` come in figura.

7

fig. 13 fine dellalgoritmo con le distanza minime

8