ALG 3

10.4. Algorytm Roy-Warshalla 253

Algorytm Roy-Warshalla może być w dość prosty sposób zmodyfikowany, tak aby dostarczyć informacji nie tylko o istnieniu drogi wiodącej od wierzchołka ,v do wierzchołkay, ale oprócz tego podać przepis którędy należy pójść...

W celu zidentyfikowania drogi (oczywiście jeśli w ogóle ona istnieje!) przyporządkujemy macierzy reprezentującej graf tzw. macierz kierowania ruchem (ang. routing) R. Jest ona zdefiniowana w sposób następujący:

•    R[x. y]=0. jeśli nie ma drogi, która wiedzie od .r do y;

•    R[x, yj^z, gdzie z oznacza „następny” wierzchołek na drodze od x do y.

Konstrukcja matiycy umożliwia w naturalny sposób odtworzenie drogi wiodącej od danego wierzchołka do innego:

route.cpp

void pisz(int x, int y, int rt(n][n]) l

int k;

if(R[x][y)==C)

cout « "Drogi nie ;ua\n"; else (

cout << x « endl; k=x;

while(k!=y) k=RLkJ ty];

cout « k « endl;

)

f

cout << endl;

f

Wiemy już, jak wypisać drogę na podstawie macierzy R, najwyższa zatem pora na przedstawienie algorytmu, który ją prawidłowo dla danego grafu wylicza.

Przedstawiona poniżej procedura route „zakłada", że matryca R przekazana jej w parametrze została zainicjowana uprzednio w następujący sposób:

•    R[x,y]=0, jeśli nic istnieje krawędź (x,y);

•    R[x,y]=y, w przeciwnym przypadku.

Zapis procedury jest ekstremalnie prosty:

void route(int R[n][n])

(

for(int x=C;x<n;x++) for(int y=0;y<n;y++!

if(R[y)[x]!—O> II wiemy jak dojść z 'y' do 'x' for(int z=0;z<n;z++)