ALGORITMUL ROY-FLOYD
STUDENTI:
NANE ANAMARIA-STEFANIA
BRUMA MARIA
INTRODUCERE
În matematică și informatică, teoria grafurilor studiază
proprietățile grafurilor. Un graf este o mulțime de
obiecte (numite noduri) legate între ele printr-o mulțime
de muchii cărora le pot fi atribuite direcții (în acest caz,
se spune că graful este orientat). Un graf poate fi
reprezentat geometric ca o mulțime de puncte legate între
ele prin linii (de obicei curbe).
INTRODUCERE
Dezvoltarea teoriei grafurilor a pornit de la probleme legate de jocuri și amuzamente matematice menite a
testa ingeniozitatea. Acestea au atras atenția unor matematicieni experimentați ca Euler, Hamilton, Cayley
, Birkhoff iar cu trecerea anilor teoria grafurilor a devenit un domeniu bogat in rezultate și de o
surprinzătoare varietate și aplicabilitate.
Grafurile au o importanță imensă în informatică, de exemplu:
• în unele problemele de sortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot
reprezenta prin noduri într-un graf;
• schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc
de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție;
• în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată
printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări,
agregări).
INTRODUCERE
In continuarea materialului prezentat vom aborda
algoritmul Roy-Floyd, un algoritm ce permite
determinarea drumurile minime într-un graf.
Algoritmul Roy-Floyd
Din punct de vedere istoric, algoritmul a fost publicat în forma
curentă de Robert Floyd în 1962. Trebuie menționat că în esență
este același algoritm cu cel publicat în 1959 de Bernard Roy. În
literatura de specialitate se regăsește deci sub diverse nume:
Algoritmul Roy-Floyd, Algoritmul lui Floyd sau uneori Algoritmul
Floyd-Warshall.
Algoritmul Roy-Floyd
Din punct de vedere al programării, algoritmul este
unul de programare dinamică (poate fi descompus în
subprobleme astfel încât fiecare subproblema este
rezolvată o singură dată iar soluția este stocată pentru a fi
folosită ulterior la rezolvarea problemei inițiale). Marele
avantaj al acestui algoritm este simplitatea sa!
Algoritmul Roy-Floyd
În cele ce urmeză considerăm cunoscute din cursurile anterioare noțiunile de
graf; graf orientat;
drum intr-un graf;
matrice de adiacență;
matricea drumurilor directe, etc.
Algoritmul Roy-Floyd
PREZENTAREA ALGORITMULUI
Ideea de bază a algoritmului este următoarea: dacă drumul minim între două
vîrfuri oarecare i și j trece printr-un vârf k, atunci drumurile de la i la k și de la
k la j sunt la rândul lor minime.
Putem deci să-i dăm lui k, pe rând, valorile 1, 2,..., n și să comparăm apoi: dij
cu dik + dkj.
Dacă suma este mai mică, drumul inițial de la i la j se poate înlocui cu cel
indirect i - k – j.
PREZENTAREA ALGORITMULUI
Cu alte cuvinte, pentru graful inițial dat, pornind de la matricea
distanțelor directe:
D = dij(0)
putem obține, într-un număr de n pași, o matrice a tuturor distanțelor
minime
dij(k) = min {dij(k-1), dik(k-1) + dkj(k-1)}
Procedura principală a algoritmului
În aceste condiții, procedura principală a algoritmului este următoarea:
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
dij(k) = min{dij(k-1) , dik(k-1) + dkj(k-1)};
iar algoritmul este deci de complexitate O(n3).
Determinarea drumurilor minime
Determinarea drumurilor minime se poate realiza și ea în cadrul
algoritmului dacă se utilizează în paralel o matrice ∆ inițializată cu:
- xi dacă dij < ∞
- dacă dij = ∞
La sfârșitul algoritmului obținem matricea ∆n unde δij este mulțimea de
vîrfuri vecine cu xj ce se gasesc pe drumurile de lungime minimă de la xi la
xj.
Exemplu-Algoritmul Roy-Floyd
În continuare ne propunem să determinăm drumurile minime pentru graful de mai jos
(pornind de la matricea distanțelor directe).
Exemplu-Algoritmul Roy-Floyd
În slide-ul precedent am scris matricea
distanțelor directe asociate grafului dat (fără
folosirea de noduri intermediare). Să căutăm
acum drumuri mai scurte între oricare două
noduri permițând pe rând utilizarea câte unui
alt nod.
Concluzie
Fiind folosit în diverse domenii (de la controlul
avioanelor de pe un anumit aeroport până la jocuri
informatice) și beneficiind de o implementare facilă
algoritmul Roy-Floyd este una dintre primele alegeri
atunci când se urmărește găsire drumului minim între un
obiect principal și o țintă anume.