372 373

Programowanie sieciowe

8.3. Najkrótsze drogi w sieci

Omówienie zagadnienia poszukiwania najkrótszych dróg w sieci rozpoczniemy od podania przykładu problemu transportowego występującego w firmie budowlanej.

Przykład 8.2

Firma budowlana prowadzi 5 inwestycji. Ze względu na konieczność codziennego przemieszczania personelu, maszyn i materiałów z centrali na poszczególne place budów istotne staje się zminimalizowanie kosztów transportu. Temu celowi służy m.in. określenie najkrótszych połączeń komunikacyjnych między biurem i znajdującym się w pobliżu centralnym magazynem firmy a poszczególnymi placami budów. Sieć dróg warunkuje możliwości połączeń komunikacyjnych. Zostały one przedstawione na rys. 8.8. Wierzchołek 1 oznacza siedzibę firmy, natomiast wierzchołki 2-6 oznaczają kolejne place budów. Wartości parametru opisującego każdą z krawędzi to długość drogi między wierzchołkami, które łączy dana krawędź. Należy znaleźć najkrótsze drogi prowadzące z siedziby firmy do kolejnych placów budów.

Przedstawiony w tym przykładzie problem minimalizacji kosztów transportu dla firmy budowlanej może być rozwiązany za pomocą algorytmu poszukiwania najkrótszych dróg w sieci.

Rysunek 8.8

Algorytm ten jest dwufazowy. W pierwszej fazie cechujemy kolejne wierzchołki. Nadane etykiety mogą być stałe lub tymczasowe. Każda etykieta ma dwie składowe. Pierwsza z nich opisuje długość najkrótszej znalezionej dotąd drogi do danego wierzchołka, druga składowa to numer wierzchołka stanowiącego początek ostatniej krawędzi należącej do tej najkrótszej drogi. W kolejnych iteracjach etykiety tymczasowe mogą być zmieniane. Dzieje się tak wówczas, gdy znajdziemy drogę lepszą od drogi znalezionej dotychczas. Jeżeli mamy pewność, że dla danego wierzchołka nie istnieje lepsza droga, to przyporządkowujemy mu etykietę stałą. Po ocechowaniu na stałe wszystkich wierzchołków przechodzimy do realizacji drugiej fazy algorytmu, w której na podstawie drugich składowych etykiet odtwarzamy przebieg najkrótszych dróg od wierzchołka początkowego do wszystkich pozostałych wierzchołków. Poniżej przedstawimy opis algorytmu.

8.3.1. Reguły postępowania przy poszukiwaniu najkrótszych dróg w sieci

Faza L Cechowanie wierzchołków Iteracja 1

Wierzchołkiem cechowanym na stałe jest wierzchołek 1. Przyporządkowujemy mu etykietę stałą [0, S | (pierwsza składowa opisuje odległość tego wierzchołka od niego samego, równą 0; litera S, występująca jako druga składowa, wskazuje na to, że jest to wierzchołek początkowy, czyli startowy). Znajdujemy krawędzie rozpoczynające się w wierzchołku początkowym. Wierzchołkom kończącym te krawędzie przyporządkowujemy etykiety tymczasowe.

Iteracja k (k ^ n)

Z wierzchołków ocechowanych tymczasowo wybieramy wierzchołek, który cechujemy na stałe. Jest to ten wierzchołek, który ma pierwszą składową najmniejszą (w przypadku niejednoznaczności wybieramy wierzchołek o najniższym numerze). Znajdujemy krawędzie prowadzące od wybranego wierzchołka do wierzchołków, które nie zostały dotychczas ocechowane na stałe. Dla każdego z nich sprawdzamy, czy droga przechodząca przez rozpatrywany wierzchołek jest lepsza od dotychczasowej. Jeżeli tak jest, zmieniamy etykietę tymczasową, jeżeli nie — etykieta tymczasowa pozostaje bez zmian. Postępowanie to powtarzamy aż do wyczerpania wszystkich możliwości.

Faza 2. Identyfikacja najkrótszych dróg

Dla kolejnych wierzchołków, rozpoczynając od wierzchołka 2, identyfikujemy krawędzie wchodzące w skład najkrótszej drogi. Do tego celu służy druga składowa etykiety stałej. Identyfikujemy kolejne krawędzie poszukiwanej drogi (rozpoczynając od ostatniej) tak długo, aż dojdziemy do wierzchołka początkowego.