376 377

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

Wyszukiwarka

Podobne podstrony:
380 381 380 Programowanie sieciowe Rysunek 8.15 W zagadnieniu maksymalnego przepływu wyróżniamy wier
370 371 370 Programowanie sieciowe Rysunek 8.4 Iteracja 4 Do zbioru wierzchołków połączonych zalicza
42451 skanuj0001 (15) 376 PROGRAMY EUROPEJSKIE a)    zdygitalizowaną bazę danych wspó
skanuj0001 (15) 376 PROGRAMY EUROPEJSKIE a)    zdygitalizowaną bazę danych współczynn
Finanse p stwa Wypych76 377 Ocena finansowa przeasięwzięć rozwojowymi m Rysunek 10.1. Poszukiwanie I
32 (376) sza duży rysunek, ilustrację lid) obrus. Uczniowie oglądają i następnie] odpowiadają na pyt
Rysunek 10 Okno ustawień programu - Opcje 3. Pojawi się kolejne okno - Kolory okna rysunku. I Opcje
Finanse p stwa Wypych76 377 Ocena finansowa przedsięwzięć rozwo/owycn Rysunek 10.1. Poszukiwanie IRR
394 395 394 Programowanie sieciowe numeracji budynków w tablicy 8.10. Wartości przy odpowiednich kra
42451 skanuj0001 (15) 376 PROGRAMY EUROPEJSKIE a)    zdygitalizowaną bazę danych wspó
<10>Informatyka + Rysunek 10. Dostęp podstawowy BRI kanału D (razem 144 kb/s), jeśli nie jest
skanuj0164 (10) Rozdział 6. o Ciągi znaków, data i czas 175 Rozdział 6. o Ciągi znaków, data i czas

więcej podobnych podstron