DOCUMENTATIE la aplicatia RoutFW

Partea I. Algoritmul de rutare Floyd-Warshall

Algoritmul rezolva drumul minim intre toate perechile pe un graf orientat G=(V,E). El se executa in timp O(V³). Pot exista arce cu costuri negative, dar vom presupune ca nu exista cicluri de cost negativ. In dezvoltarea algoritmului vom urmari pasii programarii dinamice.

Structura unui drum minim

In algoritmul Floyd-Warshall folosim o caracterizare diferita a structurii unui drum minim fata de cea folosita in algoritmii de drum minim bazati pe inmultirea matricilor. Algoritmul ia in considerare varfurile "intermediare" ale unui drum minim, unde un varf intermediar al unui drum elementar p = <v₁, v₂, .,v_l> este oricare varf v diferit de v₁ si v_l, adica orice varf din multimea .

Algoritmul Floyd-Warshall este bazat pe urmatoarea observatie. Fie V = multimea varfurilor lui G. Consideram submultimea pentru un anumit k. Pentru oricare pereche de varfuri i, j din V, consideram toate drumurile de la i la j ale caror vafuri intermediare fac parte din multimea . Fie p drumul de cost minim dintre aceste drumuri. (Drumul p este elementar deoarece presupunem ca G nu contine cicluri de cost negativ.) Algoritmul exploateaza o relatie intre drumul p si drumul minim de la i la j cu toate varfurile intermediare in multimea . Relatia depinde de statutul lui k: acesta poate fi varf intermediar sau nu a lui p.

Daca k nu este un varf intermediar al drumului p, atunci toate varfurile intermediare ale drumului p fac parte din multimea . Ca urmare, un drum minim de la varful i la varful j cu toate varfurile intermediare in multimea este, de asemenea, un drum minim de la i la j cu toate varfurile intemediare in multimea .

.

Lema. (Subdrumurile unui drum minim sunt drumuri optimale)

Fiind dat un graf orientat cu costuri G=(V,E) cu functia de cost w:E R, fie p = <v₁, v₂, .,v_k> un drum minim de la varful v₁ pana la v_k si pentru orice i si j astfel incat 1<=i<=j<=k fie p_ij = <v_i, v_i+1,.,v_j> subdrumul lui p de la varful v_i la varful v_j. Atunci p_ij este drum minim de la v_i la v_j.

Daca k este un varf intermediar al drumului p, atunci vom imparti p in p1(de la i la k) si p2(de la k la j) dupa cum se poate vedea in figura de mai sus. Din Lema rezulta ca p1 este drumul minim de la i la k cu toate varfurile intermediare in multimea . De fapt, varful k nu este un varf intermediar al drumului p₁, deci p₁ este un drum minim de la i la k cu toate varfurile in multimea . In mod similar aratam ca p2 este drum minim de la varful k la varful j cu toate varfurile intermediare in multimea .

O solutie recursiva la problema drumurilor minime intre toate perechile de varfuri

Bazandu-ne pe observatia anterioara, definim o formulare recursiva a estimarilor drumului minim. Fie d_ij^(k) costul drumului minim de la varful i la varful j cu toate varfurile intermediare in multimea . Cand k=0, un drum de la varful i la varful j, cu nici un varf intermediar al carui numar este mai mare decat 0, nu are, de fapt, nici un varf intermediar. In concluzie, acest drum contine cel mult un arc, deci d_ij⁽⁰⁾ = w_ij. O definitie recursiva este data de:

w_ij daca k = 0

d_ij^(k) =

min (d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1)) daca k >= 1

Matricea D⁽ⁿ⁾ = (d_ij⁽ⁿ⁾) contine raspunsul final, d_ij⁽ⁿ⁾ este distanta de la i la j pentru oricare i, j din V, deoarece toate nodurile intermediare se afla in multimea .

Determinarea ascendenta a costurilor drumurilor minime

Urmatoarea procedura ascendenta este bazata pe recurenta de mai sus si poate fi folosita pentru a determina valorile d_ij^(k) in ordinea valorilor crescatoare k. Intrarea ei este o matrice W de dimensiuni n x n ce reprezinta matricea costurilor. Procedura returneaza matricea D⁽ⁿ⁾ a costurilor drumurilor minime.

FLOYD-WARSHALL (W)

n = linii[W]

D⁽⁰⁾ = W

pentru k = 1, n executa

pentru i = 1,n executa

pentru j = 1,n executa

d_ij^(k) = min (d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1) )

returneaza D⁽ⁿ⁾

In figura 3 sunt prezentate matricile D^(k) determinate de algoritmul Floyd-Warshall, aplicat grafului din figura 2.

Timpul de executie al algoritmului Floyd-Warshall este determinat de cele trei cicluri pentru imbricate din liniile 3-6. Fiecare executie la liniei 6 necesita un timp O(1), deci algoritmul se executa in timp O(n³). In concluzie, algoritmul Floyd-Warshall este destul de practic, chiar daca grafurile de intrare au dimensiune medie.

Construirea unui drum minim

Exista o varietatate de metode diferite pentru construirea drumurilor minime in algoritmul Floyd-Warshall. O modalitate este de a determina matricea D a costurilor drumurilor minime si de a construi, apoi, matricea P a predecesorilor cu ajutorul matricei D. Aceasta metoda poate fi implentata astfel incat sa ruleze in timp O(n³).

Putem determina matricea P "in timp real" la fel cum algoritmul Floyd-Warshall determina matricea D^(k). Mai exact determinam un sir de matrice P⁽⁰⁾, P⁽¹⁾,., P⁽ⁿ⁾, unde P = P⁽ⁿ⁾ si p_ij^(k) este definit ca fiind predecesorul varfului j in drumul minim de la varful i cu toti predecesorii in multimea .

Putem da o formula recursiva pentru p_ij^(k). Cand k = 0, un drum minim de la i la j nu are nici un varf intermediar. Deci

NIL daca i=j sau w_ij = infinit

p_ij⁽⁰⁾  =

i daca i diferit de j sau w_ij < infinit

Pentru k>=1, daca luam in considerare drumul i k j, atunci predecesorul lui j pe care il alegem este acelasi cu predecesorul lui j pe care il alegem pe un drum minim de la k cu toate varfurile intermediare in multimea . Altfel, alegem acelasi predecesor al lui j pe care l-am ales intr-un drum minim de la i, cu toate varfurile intermediare in multimea . Mai exact pentru k>=1,

p_ij^(k-1)  daca d_ij^(k-1) <= d_ik^(k-1) + d_kj^(k-1),

p_ij^(k) =

p_kj^(k-1) daca d_ij^(k-1) > d_ik^(k-1) + d_kj^(k-1).

In figura 3 se arata sirul P^(k) pe care algoritmul rezultat il determina.

Parte a II-a. Mediul de simulare al algoritmului de rutare Floyd-Warshall

Aplicatia "RoutFW" simuleza algoritmul descris in prima parte. Functionalitatile de baza oferite sunt: editarea unui graf orientat si executia pas cu pas a algoritmului Floyd-Warshall pe graful dat.

Graful poate fi scris, respectiv incarcat de pe disk, iar editarea implica inclusiv posibilitatea de a sterege un nod sau arc.

La executia pas cu pas, algoritmul poate fi dat si cu un "pas inapoi". Matricile cost si predecesori, afisate in fereastra de rezultate sunt interactive - primesc dublu click pe un element si coloreaza in fereastra de editare drumul corespunzator nodurilor linie si coloana.

In continuare voi prezenta un screen shot al ferestrei aplicatiei cu indicatii pe ea.