374 375

374 Programowanie sieciowe

8.3.2. Kolejne iteracje

Prześledzimy przebieg kolejnych iteracji dla zadania sformułowanego w przykładzie 8.2.

Iteracja 1

Z wierzchołka początkowego o numerze 1 wychodzą trzy krawędzie: 1-2, 1-3 i 1-4 (rys. 8.8). Odległości wierzchołków kończących te krawędzie (czyli wierzchołków 2, 3 i 4) od wierzchołka początkowego są równe długościom odpowiednich krawędzi, czyli 8, 4 i 2. Ponieważ wierzchołkiem poprzedzającym w każdym z tych przypadków jest wierzchołek 1, otrzymujemy następujące etykiety tymczasowe:

dla wierzchołka 2: etykieta |8, 1], dla wierzchołka 3: etykieta [2, 1], dla wierzchołka 4: etykieta [4, 1J.

Iteracja 2

Przeglądając pierwsze składowe etykiet tymczasowych, stwierdzamy, że wierzchołkiem cechowanym na stałe będzie wierzchołek 3 (wartość pierwszej składowej rozpatrywanych etykiet tymczasowych jest dla tego wierzchołka najmniejsza). Wybór wierzchołka cechowanego na stałe przedstawiono na rys. 8.9.

Rysunek 8.9

Z wierzchołka 3 wychodzą trzy krawędzie: 3-2, 3-4 i 3-5, które rozpatrzymy po kolei.

Krawędź 3-2 prowadzi nas do wierzchołka 2. Ma on już nadaną etykietę tymczasową. Pierwszą składową tej etykiety, czyli liczbę 8, określającą uprzednio znalezioną najkrótszą drogę do wierzchołka 2, porównujemy z nową możliwością, jaką aktualnie daje nam osiągnięcie wierzchołka 2 z wierzchołka 3. Długość tej nowej drogi do wierzchołka 2 to długość uprzednio otrzymanej najkrótszej drogi do wierzchołka 3 powiększona o długość krawędzi 3-2. Mamy więc:

8 > 2+5.

Powyższa nierówność wskazuje na to, że celowe jest wykorzystanie tej nowej możliwości. Prowadzi to do zastąpienia, zgodnie z zasadami konstrukcji etykiet tymczasowych, dotychczasowej etykiety tymczasowej dla wierzchołka 2 w postaci [8, 1] nową etykietą [7, 3].

Krawędź 3-4 prowadzi nas do wierzchołka 4. Ma ona etykietę tymczasową [4, I], Widzimy, że nowa, rozpatrywana aktualnie droga do wierzchołka 4 przez wierzchołek 3 jest krótsza, gdyż wynosi:

2+ 1 <4,

gdzie 4 to uprzednio znaleziona najkrótsza droga do wierzchołka 4. Tak więc również w wierzchołku 4 następuje zmiana etykiety tymczasowej. Nowa etykieta tymczasowa dla wierzchołka 4 ma składowe: [3, 3],

Krawędź 3-5 prowadzi do wierzchołka 5, który nie był dotychczas cechowany. Znaleziona droga do wierzchołka 5, prowadząca przez wierzchołek 3, jest sumą najkrótszej drogi do wierzchołka 3 (wynoszącej 2) oraz długości krawędzi 3-5 (wynoszącej 7), czyli jest równa 9. Nowo utworzona etykieta tymczasowa dla wierzchołka 5 ma składowe: [9, 3],

Jednocześnie stwierdzamy, że po dokonaniu zmian etykiet tymczasowych w wierzchołkach 3 i 4 oraz po zaetykietowaniu nowego wierzchołka 5 zbiór etykiet tymczasowych (uwzględniający etykiety tymczasowe otrzymane od początku rozwiązywania zadania) jest następujący:

dla wierzchołka 2: etykieta f7, 3j, dla wierzchołka 4: etykieta [3, 3], dla wierzchołka 5: etykieta [9, 3].

Iteracja 3

Przeglądając ponownie pierwsze składowe etykiet tymczasowych, stwierdzamy, że wierzchołkiem cechowanym na stałe będzie wierzchołek 4. Wybór tego wierzchołka ilustruje rys. 8.10.