Floyd-Warshallov algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Floyd-Warshallov algoritem reši problem iskanja najkrajših poti med vsemi pari vozlišč v usmerjenem, uteženem grafu. Uteži so poljubne. Graf ne sme vsebovati negativnih ciklov.
Algoritem uporablja princip dinamičnega programiranja.

Vsebina

Algoritem

Imamo usmerjen, utežen graf G = (V,E).

d(i,j; k) ... teža najkrajše poti od i do j, katera notranja vozlišča so vsebovana v množici {1,...,k}

Zanima nas d(i,j; |V(G)|).

Dinamični pristop:

  • za vsak par i, j\inV(G) pogledamo vse poti od i do j, katera notranja vozlišča so vsebovana v množici {1,...,k}
  • če k ni vmesno vozlišče poti od i do j, potem gre pot skozi vozlišča {1,...,k − 1}. Torej je najkrajša pot od i do j prek {1,...,k − 1}, tudi najkrajša pot prek vozlišč {1,...,k}
  • če k je vmesno vozlišče poti od i do j, potem pot razbijemo na dve poti. Pot p1 je najkrajša pot od i do k prek {1,...,k − 1}, p2 pa najkrajša pot od k do j prek {1,...,k − 1}

Rekurzivna enačba:

d(i,j; 0) = w(i,j)

d(i,j; k) = min{d(i,j; k-1), d(i,k; k-1)+d(k,j; k-1)}

Shema algoritma

FLOYD-WARHALL(W)
//W...matrika uteži
D(0) = W
for k=1 to |V(G)| do
  for i=1 to |V(G)| do
    for j=1 to |V(G)| do
       d(i,j; k) = min{d(i,j; k-1), d(i,k; k-1)+d(k,j; k-1)}
return D(|V(G)|)


Časovna zahtevnost: O(|V|3)

Konstrukcija poti

Poti predstavimo z matriko prednikov Π(k). V matriki bo i-ta vrstica predstavljala drevo najkrajših poti z začetkom v vozlišču i.

π(i,j;k) ... prednik od j na najkrajši poti od i do j z vmesnimi vozlišči {1,...k}

Rekurzivna enačba:

\pi (i,j; 0) =  \begin{cases} nil, & i=j \\ i, &  i\neq j\end{cases}

\pi (i,j; k) =  \begin{cases} \pi (i,j; k-1) , & d(i,j; k-1)\leq   d(i,k; k-1)+d(k,j; k-1)  \\  \pi (k,j; k-1), &  d(i,j; k-1)>d(i,k; k-1)+d(k,j; k-1)\end{cases}

Matriko prednikov lahko vgradimo v algoritem.Na zacčetku nastavimo Π(0) in tekom algoritma, ko spreminjamo D popravimo tudi Π.

Primer

D(0)
0 3 8 -4
0 1 7
4 0
2 -5 0
6 0
Π(0)
nil 1 1 nil 1
nil nil nil 2 2
nil 3 nil nil nil
4 nil 4 nil nil
nil nil nil 5 nil
D(1)
0 3 8 -4
0 1 7
4 0
2 5 -5 0 -2
6 0
Π(1)
nil 1 1 nil 1
nil nil nil 2 2
nil 3 nil nil nil
4 1 4 nil nil
nil nil nil 5 nil
D(2)
0 3 8 4 -4
0 1 7
4 0 5 11
2 5 -5 0 -2
6 0
Π(2)
nil 1 1 2 1
nil nil nil 2 2
nil 3 nil 2 2
4 1 4 nil 1
nil nil nil 5 nil
D(3)
0 3 8 4 -4
0 1 7
4 0 5 11
2 -1 -5 0 -2
6 0
Π(3)
nil 1 1 2 1
nil nil nil 2 2
nil 3 nil 2 2
4 3 4 nil 1
nil nil nil 5 nil
D(4)
0 3 -1 4 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0
Π(4)
nil 1 4 2 1
4 nil 4 2 1
4 3 nil 2 1
4 3 4 nil 1
4 3 4 5 nil
D(5)
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0
Π(5)
nil 3 4 5 1
4 nil 4 2 1
4 3 nil 2 1
4 3 4 nil 1
4 3 4 5 nil

Na primer, da nas zanima najkrajša pot od vozlišč 5 do vozlišča 2. Teža te poti je 5, sama pot poteka skozi vozlišča
5\rightarrow 4\rightarrow 3\rightarrow 2.

Literatura

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to algorithms

Osebna orodja