378 379

378 Programowanie sieciowe

Jedynym wierzchołkiem nie ocechowanym na stałe i osiągalnym z wierzchołka 2 jest wierzchołek 6. Długość najkrótszej drogi do wierzchołka 6, przechodzącej przez wierzchołek 2, wynosi 6 + 6 > 11, czyli tym razem nie uzyskaliśmy poprawy długości drogi do wierzchołka 6, przechodzącej przez wierzchołek 2. Etykieta tymczasowa dla wierzchołka 6 pozostaje więc bez zmian.

W aktualnym zbiorze etykiet tymczasowych mamy teraz tylko jedną etykietę — dla wierzchołka 6: etykieta [11, 5].

Iteracja 6

Cechujemy na stałe wierzchołek 6 (rys. 8.13).

Rysunek 8.13

Ponieważ wszystkie wierzchołki zostały ocechowane na stałe, pierwsza faza algorytmu została zakończona.

Obecnie przejdziemy do drugiej fazy algorytmu, polegającej na identyfikacji najkrótszych dróg. Przedstawimy przykładowo konstrukcję drogi dla wierzchołka 2. Druga składowa etykiety stałej dla tego wierzchołka, równa 4, wskazuje na to. że ostatni odcinek konstruowanej najkrótszej drogi rozpoczyna się w wierzchołku 4. Tak więc ostatni odcinek tej drogi to krawędź 4-2.

Z kolei najkrótsza droga do wierzchołka 4 prowadzi z wierzchołka 3, a do niego dochodzimy bezpośrednio z wierzchołka 1. Tak więc najkrótsza droga do wierzchołka 2 składa się z następujących krawędzi: 1-3, 3-4, 4-2. Drogę tę zapiszemy jako ciąg wierzchołków będących początkami i końcami składających się na nią krawędzi, czyli 1 -3-4-2. Proces konstrukcji tej drogi ilustruje rys. 8.14.

Rysunek 8.14

Pozostałe najkrótsze drogi, znalezione w taki sam sposób, przedstawiono na rys. 8.14.

8.4. Maksymalny przepływ w sieci

Algorytm maksymalnego przepływu w sieci można zastosować w organizacji transportu, co ilustruje przykład 8.3.

Przykład 8.3

Natężenie pojazdów przejeżdżających przez pewien odcinek autostrady w godzinach szczytu komunikacyjnego wynosi 1500 pojazdów/h. Ze względu na konieczność przeprowadzenia remontu tego odcinka zostanie on okresowo wyłączony z ruchu. Możliwości objazdu obejmują pewne odcinki dróg o różnym standardzie nawierzchni; są one również zróżnicowane pod względem ograniczeń prędkości. Powoduje to różne przepustowości tych odcinków dróg. Rozpatrywana alternatywna sieć transportowa, która zastąpi okresowo możliwość wykorzystania autostrady między punktami 1 i 7, została przedstawiona na rys. 8.15.

Każda krawędź została opisana za pomocą dwóch parametrów, określających możliwości przepływu w obydwu kierunkach. Należy wyznaczyć maksymalny przepływ w rozpatrywanej sieci i ustalić, czy jest on wystarczający dla spodziewanego natężenia ruchu. Należy również wyznaczyć trasy, zapewniające ten maksymalny przepływ.

Wyszukiwarka

Podobne podstrony:
karta pracy 1 Przyjrzyj się poniższym obrazkom. Co jest na nich prawdą, a co nie? Skreśl na czerwono
etyka msroda1 230 Henryk ELZENBERG musi się dać /definiować w terminach woli. nie wskazuje na istni
Opanowałam cały materiał na egzaminz filozofii ...ale nie poszłam na niego, bo życie jest bez sensu
etyka msroda1 230 Henryk ELZENBERG musi się dać zdefiniować w terminach woli. nie wskazuje na istni
62119 skanowanie0203 XV.a ŚPIEW SKOWRONKA Nie mówcie na mój Hymn: „to jest nic wobec Boga”: albowiem
Numeracja torów, kierunki parzyste i nie parzyste. Na linii kolejowej ważny jest tzw. punkt początko
skanuj0002 (14) 378 PROGRAMY EUROPEJSKIE W banku informacyjnym CORINE biotopes znajdują się informac
22287 skanuj0002 (14) 378 PROGRAMY EUROPEJSKIE W banku informacyjnym CORINE biotopes znajdują się in
79794 skanuj0007 (378) terminy „język” — „mowa” — „tekst” nie oznaczają pojęć tożsamych (por. uwagi
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
skanuj0022 (41) —    Tylko uważa j z tym programem we Fkoenep. Żebyś nie przeide
skanuj0022 (41) —    Tylko uważa j z tym programem we Fkoenep. Żebyś nie przeide

więcej podobnych podstron