ALG 6

256 Rozdział 10. Elementy algorytmiki grali!

Brak możliwości odtworzenia optymalnej drogi jest dość istotną wadą, ! gdyż o ile w przypadku małych grafów (takich jak ten z rysunku 10 - 9) możemy ją ewentualnie odczytać sami, to przy naprawdę dużych grafach jest to ] praktycznie niewykonalne.

Potrzebna nam jest zatem jakaś prosta modyfikacja algorytmu Floyda, która nie zmieniając jego zasadniczej idei, umożliwi zapamiętanie drogi.

Jak się okazuje, rozwiązanie nie jest trudne. Do oryginalnego algorytmu (patrz I listing wyżej) należy wprowadzić następującą poprawkę:

if( g[i][k)+g[k]tj]<g[i][j])

(

g[i] [j1=g t i] [k]+g[k] [j] ;

R [ i] (j]=k;

>

Optymalna droga będzie zapamiętywana w matrycy kierowania ruchem R. Czytelnikowi nie powinno sprawić zbytniego kłopotu napisanie procedury, która odtwarza znajdującą się w niej drogę. Załóżmy, że początkowo matryca R jest wyzerowana. Aby odtworzyć optymalną drogę od wierzchołka i do wierzchołka /, patrzymy na wartość P[i][j]- Jeśli jest ona równa zero, to mamy do czynienia z przypadkiem elementarnym, tzn. z krawędzią, którą należy przejść. Jeśli nie, to droga wiedzie od / do P[i][j] i następnie od P[i][j] do /. Z uwagi na to. że powyższe dwie „pod-drogi” mogą nie być elementarne, łatwo zauważyć rekurcncyjny charakter procedury.

Liczę na to. że Czytelnik nie będzie miał kłopotów z jej stworzeniem... w ramach pożytecznego ćwiczenia!