Drumuri în Grafuri

Fie G=(V,M) graf orientat cu n=|V|, m=|M|. Fie A matricea sa de adiacenţă.

Considerăm şirul de matrici:

a cărui semnificaţie este următoarea:

Propoziţia 1. Ak(i,j) = numărul drumurilor de lungime k de la i la j.

- pentru k=1: evident.

- k-1 k : , unde s este penultimul vârf din drumul de la i la j; pentru fiecare s cu A(s,j)=1, la sumă se adaugă numărul drumurilor de lungime k-1 de la i la s, adică numărul drumurilor de lungime k de la i la j având pe s ca penultim vârf.

În continuare dorim să determinăm numai existenţa drumurilor de lungime k. Considerăm şirul de matrici:

unde

a cărui semnificaţie este următoarea (elementele matricilor sunt 0 sau 1):

Propoziţia 2. A(k)(i,j)=1 există drum de lungime k de la i la j.

Demonstraţia se face prin inducţie ca mai sus.

Definim matricea drumurilor D prin:

D(i,j)=1 drum de la i la j.

D=A(1) ... A(n-1), deoarece dacă există un drum de la i la j, există şi un drum de lungime cel mult egală cu n-1 de la i la j.

Construcţiile matricilor de mai sus necesită un timp de ordinul O(n4).

Vom căuta să obţinem un timp de executare mai bun, inclusiv pentru cazul în care lungimea arcelor este oarecare (în cele de mai sus s-a presupus implicit că arcele au lungimea egală cu 1).

În continuare, fiecare arc <i,j> va avea o etichetă et(<i,j>) strict pozitivă, ce reprezintă lungimea arcului.

Considerăm

şi şirul de matrici:

Propoziţia 3. Pn este matricea celor mai scurte drumuri.

Vom demonstra prin inducţie după k următoarea afirmaţie:

Pk(i,j) = lungimea celui mai scurt drum de la i la j în care numerele de ordine ale nodurilor intermediare sunt cel mult egale cu k.

- pentru k=0: evident (nu există vârfuri intermediare).

- k-1 k : Considerăm un drum de lungime minimă de la i la j.

Dacă drumul nu trece prin k, Pk(i,j)=Pk-1(i,j).

Dacă drumul trece prin k, el va trece o singură dată prin k (are lungime minimă) şi în drumurile de lungime minimă de la i la k şi de la k la j vârful k nu apare ca vârf intermediar, deci Pk(i,j)=Pk-1(i,k)+Pk-1(k,j).

Observaţii:

1) s-a folosit metoda programării dinamice;

2) Pk(i,i)=0;

3) Pk(i,k)=Pk-1(i,k) şi Pk(k,j)=Pk-1(k,j), deci la trecerea de la Pk-1 la Pk linia k şi coloana k rămân neschimbate.

Rezultă că putem folosi o singură matrice. Ajungem astfel la algoritmul Floyd-Warshall:

for k=1,n

for i=i,n

for j=1,n

P(i,j) min {P(i,j),P(i,k)+P(k,j)}

Timpul de executare este evident de ordinul O(n3).