ALG 2

252

warshall.cpp

Rozdział 10, Elementy algorytmiki grafów

Jest możliwe udowodnienie, że domknięcie przechodnie grafu może być obliczone poprzez sukcesywną kompozycję operacji 0 , tzn. dla grafu o wierzchołkach /... n:

Algorytm zapisuje się bardzo prosto w C++:

void warshalllint ej[n][n]) i

for(int x=Q;x<n;xH) for(lnt y=0;y<n;y++) forfint z-0;z<n;x++)

if (glyj .zj ==0)

g[y] Izi=g[y] [x] *g[x] [z];

)

W celu dokładnego zrozumienia tego programu prześledźmy jego wykonanie na przykładzie prostego grafu 5-węzłowego przedstawionego na rysunku 10-6.

0    12    3    4

	X		X
			X
	X
		X
	X

0    12    3    4

	X	X	X
	X	X	X
	X	\	X
	X	X	X
	X	X	X

Efekt wykonanie algorytmu Roy-WatshaUa

Rys. 10- 6.

(Zamiast tradycyjnych .jedynek” na rysunku zostały użyte znaki Aj.

Z tablicy na rysunku 10-6 możemy odczytać m in. następujące informacje:

•    nie jest możliwe dojście do węzłów o numerach 0 i 4\

•    : węzła o numerze 1 możemy dojść do 2, 3 i... 1 (natrafiliśmy na tzw. obwód zamknięty).

Nawet na tak prostym przykładzie możemy już co najmniej „poczuć” ogromne możliwości, jakie oferuje nam algorytm Roy-Warshalla.

Jest on niesłychanie prosty zarówno ideowo, jak i w zapisie, co klasyfikuje go do grona algorytmów, które prywatnie określam jako „eleganckie” (J. Bentley używa do tego celu wyrażenia „perła” programistyczna).