Tehnici de determinare a drumurilor minime in grafuri. Algoritmul lui Dijkstra si algoritmul lui Floyd

1. Scopul lucrarii il reprezinta prezentarea modului de determinare a drumurilor minime in grafuri ponderate utilizand algoritmul lui Dijkstra sau cel al lui Floyd.

2. Aspecte teoretice.

2.1. Algoritmul lui Dijkstra

O problema des abordata mai ales in contextul grafurilor orientate si ponderate o reprezinta determinarea drumurilor minime cu origine unica: adica de a determina costurile celui mai scurt drum de la un anumit nod de origine la toate celelalte noduri ale grafului. Un caz particular al problemei anterioare o reprezinta determinarea drumului cel mai scurt intre doua noduri precizate dintr-un graf.

Grafurile orientate sunt grafuri in care arcele au un singur sens. Din punct de vedere al structurilor de date utilizate, trebuie tinut cont de faptul ca grafurile orientate sunt simple restrictii ale grafurilor neorientate. Este insa posibil ca intre doua noduri sa existe doua arce avind sensuri opuse.

Astfel, in cazul reprezentarii prin matrici de adiacenta, arcul de la nodul x la nodul y se va marca o singura data, prin valoarea adevarat a elementului matricii din linia x, coloana y, dar nu si a elementului din linia y, coloana x, matricea fiind in acest caz ne-simetrica. In mod similar, in reprezentarea bazata pe liste de adiacenta, arcul de la x la y este reprezentat prin insertia nodului y in lista de adiacente a nodului x.

Grafurile orientate pot fi si ponderate. Un exemplu de astfel de graf, orientat si ponderat, este prezentat in figura 11.1. In figura 11.2 sunt reprezentate drumurile de cost minim de la nodul 1 la fiecare dintre celelalte noduri, pentru acest graf.

Algoritmul lui Dijkstra se bazeaza pe o multime, U, in care se pastreaza nodurile pentru care cea mai scurta distanta la nodul origine este deja cunoscuta. Initial, U contine numai nodul origine; la fiecare pas se adauga inca un nod care nu apartine lui U si a carui distanta de la origine este cit mai scurta posibil.

Exista intotdeauna un drum minim, numit drum special, care leaga originea de nodul x si care trece numai prin nodurile continute de multimea U. Pentru inregistrarea lungimii drumurilor speciale corespunzatoare tuturor nodurilor grafului se utilizeaza tabloul costMin, care este actualizat la fiecare pas. Initial, acesta contine pentru nodul x, costul muchiei de la origine la nodul x. Astfel, in tabloul arc, care contine costurile arcelor grafului, in cazul in care arcul (i, j) nu exista, se va initializa arc[i, j] = mare (o valoare mare, mai mare decat orice cost). Vom folosi si un tablou, parinte,  in care vom memora pentru nodul i, nodul anterior lui din drumul minim. Acest tablou se initializeaza cu indicele nodului origine pentru toate celelalte noduri.

Multimea nodurilor alese, U, se memoreaza in tabloul marc, elementul de pe pozitia i avand valoarea adevarat daca nodul a fost ales si fals - daca nu a fost ales.

La adaugarea unui nou nod (k) in U, se verifica pentru fiecare nod neales inca, i, daca drumul special de la origine (o) la i, care trece prin k are costul mai mic decat drumul special gasit pentru i pana la momentul respectiv. Daca da, noul drum special va fi cel prin k (figura 11.3 - cu linie intrerupta sunt reprezentate drumurile speciale, iar nodurile alese sunt marcate cu *) si se vor actualiza corespunzator tablourile parinte si costMin (notat cu c in figura) pentru nodul i.

Arborele de acoperire minim rezultat in urma algoritmului va fi memorat in tabloul parinte, in reprezentarea indicator spre parinte. Pentru a gasi drumul minim de la nodul origine la un alt nod al grafului, se poate merge in sens invers mergand pe inlantuirile indicate de tabloul parinte. Codul prezentat in continuare afiseaza drumurile minime din origine la toate celelalte noduri:

void AfisDrum(int k)

printf('nDrumurile de cost minim:');

for(i=1;i<nrN;i++)

Costul drumului minim de la origine la nodul i va fi continut in tabloul costMin, respectiv costMin[i]

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

In figura 11.4 sunt prezentati pasii pentru determinarea drumurilor minime cu originea 1 (initial U = ) pentru graful din figura 11.1 (linia intrerupta reprezinta drumurile speciale gasite pana la momentul respectiv, muchiile care conduc la alte drumuri cu cost mai mare nu mai sunt reprezentate, iar nodurile alese sunt marcate cu *). Sunt date valorile elementelor tablourilor marc, parinte si costMin la fiecare pas. Pentru o urmarire mai usoara, pentru tabloul parinte am tiparit pe fiecare pozitie cheia nodului parintelui si nu indicele lui in matrice (cu M am simbolizat valoarea mare).

Drumurile de cost minim vor fi:

de la 1 la 2 (cost 2): 1 2

de la 1 la 3 (cost 1): 1 3

de la 1 la 4 (cost 3): 1 3 4

de la 1 la 5 (cost 7): 1 3 4 7 6 5

de la 1 la 6 (cost 6): 1 3 4 7 6

de la 1 la 7 (cost 5): 1 3 4 7

Astfel, pentru graful din figura 11.1, aplicarea algoritmului lui Dijkstra conduce la arborele de acoperire format din arcele: (1, 3), (1, 2), (3, 4), (4, 7), (7, 6) si (6, 5), reprezentat in figura 11.2.

Implementarea algoritmului bazata pe observatiile de mai sus este urmatoarea:

void Dijkstra()

parinte[0] = -1;

marc[0] = true;

for(j=0;j<nrN-1;j++)

printf('(%d, %d) ',

nod[parinte[idxMin]].cheie, nod[idxMin].cheie);

marc[idxMin] = true;//marcam nodul ca inclus

for(k=1;k<nrN;k++)//actualizam parinte si costMin

if(marc[k]==false)//pentru nodurile nealese

if(costMin[idxMin]+arc[idxMin][k] < costMin[k])

}

2.2. Algoritmul lui Floyd

O problema derivata din problema drumurilor minime cu origine unica, pe care algoritmul lui Dijkstra prezentat mai sus o rezolva, o reprezinta problema determinarii drumurilor minime corespunzatoare tuturor perechilor de noduri. Evident, aceasta problema poate fi rezolvata si cu ajutorul algoritmului lui Dijkstra, considerand pe rand, fiecare nod al grafului drept origine. O alta posibilitate o reprezinta algoritmul lui Floyd.

Acesta utilizeaza o matrice a de dimensiuni nrNoduri x nrNoduri, unde memoreaza lungimile drumurilor minime. Initial, a[i, j] = cost[i, j], pentru i != j; daca nu exista arc de la i la j, cost[i, j] = mare. Elementele diagonalei principale in matricea a se initializeaza la zero.

Algoritmul executa nrNoduri iteratii asupra matricii a, rezultand pe rand matricile a₁, a₂, , a_nrNoduri. Dupa cea de-a k-a iteratie, a[i, j] va contine costul drumului minim de la i la j, care nu trece prin nici un nod cu numar mai mare decat k, notat cu a_k[i, j]
(figura 11.5). Astfel, pentru calcul lui a_k[i, j], se compara a_k-1[i, j], adica costul drumului de la i la j fara a trece prin nodul k, si nici printr-un alt nod cu numar mai mare decat k, cu a_k-1[i, k] + a_k-1[k, j], adica costul drumului de la i la k insumat cu costul drumului de la k la j, fara a trece prin nici un nod cu numar mai mare sau egal cu k. Daca acesta din urma se dovedeste a fi mai scurt, atunci costul acestuia se atribuie lui a_k[i, j]; altfel, acesta ramane neschimbat.

Implementarea algoritmului prezentat mai sus este urmatoarea - a este arc:

void Floyd()

}

Pe langa determinarea costurilor drumurilor minime, algoritmul determina si traseul acestora, utilizand in acest scop o alta matrice, numita drum, in cadrul careia drum[i, j] memoreaza acel nod k care conduce la cea mai mica valoare a[i, j]. Functia de mai jos este utilizata in scopul afisarii traseului drumului minim de la nodul i la nodul j (afiseaza nodurile intermediare):

void AfisDrum(int i, int j)

Aplicand algoritmul pentru graful din figura 11.1, in final obtinem (la matricea drumurilor am reprezentat cheia, nu indicele):

Din matricea putem reconstitui drumul minim (drum[i, j] = 0 inseamna ca intre i si j exista legatura directa), asa ca in functia AfisDrum. De exemplu,

drum[5, 6](=7) =

= drum[5, 7](=4), 7, drum[7, 6](=0) =

= drum[5, 4](=3), 4, drum[4, 7](=0), 7 =

= drum[5, 3](=2), 3, drum[3, 4](=0), 4, 7 =

= drum[5, 2](=0), 2, drum[2, 3](=0), 3, 4, 7=

= 2, 3, 4, 7

Acest drum are costul a[5, 6] = 11.

3. Problema rezolvata

Se dau n orase, precum si costul unei calatorii directe cu avionul dintr-un oras in altul (daca exista o astfel de cursa). Intre x si y nu exista neaparat cursa bidirectionala, iar costul calatoriei din x in y nu este neaparat identic cu cel al calatoriei din y in x. Sa se afiseze costul celei mai ieftine calatorii intre fiecare doua orase pentru care se poate ajunge cu avionul din unul in altul, precum si orasele in care se face escala.

Rezolvare

Problema se rezolva cu algoritmul lui Floyd. Datele problemei vor fi citite dintr-un fisier cu formatul: numarul de curse directe, apoi, pentru fiecare cursa directa: identificatorii celor doua orase (de pornire, respectiv, de sosire) si costul conectarii (identificatorii si costul se considera a fi un numere intregi). Pentru graful din figura 11.1 fisierul arata astfel:

13 1 2 2 1 3 1 4 1 8 2 3 4 2 5 6 5 2 2 3 4 2 3 5 8 3 6 7 6 4 3 4 7 2 6 5 1

7 6 1

Programul functioneaza si daca graful nu este conex. Daca graful contine noduri izolate, in fisier vom avea, de exemplu, pentru un nod izolat cu cheia 8: 8 8 0    

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define nrMaxN 20

#define mare 2000

typedef struct _nodGnodG;

nodG nod[nrMaxN];

int arc[nrMaxN][nrMaxN], nrN, nrA, drum[nrMaxN][nrMaxN];

int m[3], i, j, k;

FILE *f;

int CautaNod(int k)

void AfisImplGraf(void)

void Floyd()

}

void AfisDrum(int i, int j)

int main(void)

fscanf(f, '%d', &nrA);

nrN = 0;//nr. de noduri

for(i=0;i<nrA;i++)

}

arc[p[0]][p[1]] = m[2];//adaug muchia

}

fclose(f);

AfisImplGraf();

Floyd();

printf('nCalatoriile cele mai ieftine:');

for(i=0;i<nrN;i++)

}

getch();

return 0;

4. Probleme propuse

4.1. Se da o harta care contine localizarea mai multor magazine din cadrul unui centru comercial, impreuna cu strazile care leaga reteaua de magazine. Pentru fiecare strada se specifica lungimea acesteia, precum si daca este sau nu cu sens unic.

dandu-se doua magazine, sa se determine si sa se afiseze drumul cel mai scurt intre ele. Analizati rezultatul obtinut cu cel care se obtine pentru cazul in care s-ar permite circulatia in ambele sensuri pentru toate drumurile;

sa se determine si sa se afiseze care este magazinul cel mai apropiat de toate celelalte (suma distantelor este minima).

4.2. Sa se scrie un program care determina daca un graf dat este arbore. In caz afirmativ, desemnati drept radacina un nod pentru care arborele astfel obtinut sa aiba inaltime minima.

BIBLIOGRAFIE

V. Cretu, Structuri de date si tehnici de programare - curs - Universitatea Politehnica Timisoara, 1987

G. H. Gonnet, R. Baeza-Yates, Handbook of Algorithms and Data Structures, 2nd Edition, Addison-Wesley, 1991

V. Cretu,  Structuri de date si tehnici de programare avansate - curs - Universitatea Politehnica Timisoara, 1992

V. Cristea, I. Athanasiu, E. Kalisz, V. Iorga, Tehnici de programare, Editura Teora, 1993

T. Sorin, Tehnici de programare, Editura Teora, 1995

D. E. Knuth, The Art of Computer Programming, Vol.1: Fundamental Algorithms, 2nd Edition, Addison-Wesley, 1997

M. Waite, R. Lafore, Structuri de date si algoritmi in JAVA, Editura Teora, 1998

D. E. Knuth, The Art of Computer Programming, Vol.3: Sorting and Searching, 2nd Edition, Addison-Wesley, 1998

M. A. Weiss, Data Structures & Algorithms in C++, Addison-Wesley, 1999

V. I. Cretu, Structuri de date si algoritmi, Editura Orizonturi Universitare, Timisoara, 2000