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.