ALG 4

254 RozdziaMO. Elementy algorylmiki jiafa

if<R[y][z)==0 && R(X][Z]!=C)

Rly)[z)=R[y][x];

)

Algorytm jest oczywistą wariacją algorytmu poznanego uprzednio i wyglądi podobnie jak on niewinnie... jednak matematyczny dowód na to, że działa poprawnie, bynajmniej nie jest prosty.

Popatrzmy na efekt wykonania procedury roule dla grafu przedstawionego na rysunku 10-7

Droga od (I do 2: 0.1 1 2 Droga od I do 0: Drogi nic ma Droga od I do 5: 1 2 4 5 Droga od 2 do 0: Drogi nic ma Droga od 4 do 2:4 5 2 Droga od 5 do 3: Drogi nie ma

Rys. 10- 7.

Poszukiwanie dragi w grafie

Kolejnym problemem, który' omówimy, jest znajdowanie w grafie drogi optymalnej pod względem kosztów.

10.5.Algorytm Floyda

Nietrudno jest domyślić się, że nasze nowe zadanie będzie wymagało użycia grafów, które charakteryzują się przypisaniem wartości liczbowych swoim krawędziom.

Algorytm Floyda zaprezentujemy przy użyciu następujących założeń:

• Dysponujemy matrycą W, w której są zapamiętane wartości przypisane krawędziom grafu: