376 377

376 Programowanie sieciowe

Rysunek 8.10

FI - ptMttoc

Iteracja 3

NAJKRÓTSZE DK0G1 U SIECI RofcutazyuAnłc ztułftuirt

DROGA.ZOO

Uskrtż wierzchołek cer.houatiy na stałe

Z wierzchołka tego prowadzą 3 krawędzie do wierzchołków nieocechowanych na stałe. Są to krawędzie 4-2, 4-5 i 4-6. Rozpatrzymy je po kolei.

Krawędź 4-2 prowadzi do wierzchołka 2 zaetykietowanego tymczasowo. Nowa droga do wierzchołka 2, prowadząca przez wierzchołek 4, jest krótsza od uprzednio otrzymanej drogi (3 + 3 < 7), stąd nastąpi zmiana etykiety tymczasowej w wierzchołku 2. Nowa etykieta ma postać: [6, 4].

Zmiana nastąpi również dla wierzchołka 5, gdyż nowa droga o długości 3 + 1 .= -4 jest krótsza od uprzednio znalezionej drogi dla wierzchołka 5. Nowa etykieta dla tego wierzchołka ma postać: [4, 4],

Wierzchołek 6 nie był uprzednio cechowany. Znaleziona droga do wierzchołka 6, prowadząca przez wierzchołek 4, ma długość 3+10, stąd etykieta tymczasowa dla tego wierzchołka ma postać: [13, 4].

Zbiór etykiet tymczasowych ma obecnie postać:

dla wierzchołka 2: etykieta [6, 4], dla wierzchołka 5: etykieta [4, 4], dla wierzchołka 6: etykieta [13, 4],

Iteracja 4

Wierzchołkiem cechowanym na stałe jest obecnie wierzchołek 5 (rys. 8.11). Jedynym wierzchołkiem nie ocechowanym na stałe i osiągalnym z wierzchołka 5 jest wierzchołek 6. Droga prowadząca do wierzchołka 6 przez wierzchołek 5 jest krótsza od uprzednio znalezionej (4 + 7 < 13), stąd zmieniamy etykietę tymczasową w wierzchołku 6. Nowa etykieta tymczasowa ma postać: [11, 5|.

Rysunek 8.1 I

Aktualny zbiór etykiet tymczasowych jest następujący:

dla wierzchołka 2: etykieta [6, 4], dla wierzchołka 6: etykieta [I I, 5[.

Iteracja 5

Wierzchołkiem cechowanym na stałe jest obecnie wierzchołek 2 (rys. 8.12). Rysunek 8.12