ALG 1

10.3. Podstawowe operacje na grafach 251

Jeśli umiemy dokonać domknięcia przechodniego grafu, to umiemy odpowiedzieć na ważne pytanie, czy możliwe jest przejście po krawędziach grafu od jednego wierzchołka do drugiego. Zauważmy, żc domknięcie przechodnie nie daje przepisu na przejście od danego wierzchołka do wierzchołka y: dowiadujemy się tylko, że jest to możliwe.

Jednym z możliwych sposobów na obliczenie domknięcia przechodniego grafu jest wyliczenie go w sposób przedstawiony poniżej:

G^ł=GuC^J+...łG".

(n oznacza ilość wierzchołków grafu, czyli nieco formalniej // -|Aj).

Zaletą powyższego algorytmu jest prostota zapisu, wadą - czego nietrudno się domyślić - złożoność realizacji i duży koszt otrzymywanych algorytmów.

Czytelnik dysponujący dużą ilością wolnego czasu może bez zbytniego wysiłku wymyślić co najmniej jeden algorytm, który realizuje domknięcie przechodnie wg powyższego przepisu. Warto może jednak z góry uprzedzić, że nic będzie to miało specjalnego sensu, gdyż istnieje inny algorytm, który przewyższa jakością wszelkie wariacje algorytmów otrzymanych na podstawie „potęgowania” grafów. Jest to słynny algorytm Roy-Warshalla, który zostanie omówiony w paragrafie następnym.

10.4.Algorytm Roy-Warshalla

Algorytm omawiany w tym paragrafie charakteryzuje się kilkoma cechami, które powodują, że w zasadzie jest on bezkonkurencyjny, jeśli chodzi o obliczanie domknięcia przechodniego grafu. Przede wszystkim nie używa on żadnych grafów dodatkowych (czego nie da się uniknąć w przypadku algorytmów opartych na potęgowaniu), a ponadto pozwala dość łatwo odtworzyć drogę, którą należy pójść, aby przejść po krawędziach od jednego wierzchołka do drugiego.

Algorytm bazuje na operacji 0 , która dla grafu (i=(X, I) jest zdefiniowana w sposób następujący:

0_A = ru(y,z)|(.v.&)e T oraz {k,y)eY.

Zapis powyższy oznacza, że dla danego wierzchołka k do zbioru krawędzi Y dorzucamy kraw ędzie łączące poprzedniki i następniki tego wierzchołka.