Постановка задачі

Розглянемо телекомунікаційну мережу у вигляді графу G = (N, A), де N = {1, 2, …, n} – множина вузлів, A – множина дуг. Вважаємо, що ця мережа має одне інформаційне джерело – вузол s та один стік – вузол t.

Цілочисельна функція f_ij, визначена на множині A, називається потоком в мережі G = (N, A), якщо:

для всіх (i, j) Î A (1.1)

для всіх i Î N, (1.2)

Згідно цього визначення, якщо вузол j не виступає ні стоком, на джерелом, то величина потоку, що втікає в нього, повинна дорівнювати величині потоку, що витікає з нього, тобто виконуватися правило збереження потоку (1.2).

Однією з найбільш важливих потокових задач є задача знаходження шляху з джерела до стоку такого, що вартість (час) проходження потоку заданої величини по цьому шляху буде мінімальна. Припустимо, що кожній дузі (i, j) заданої мережі відповідає деяке число , що називається узагальненою вартістю дуги. Фіктивним, або безкоштовним, дугам приписується вартість , а кожній парі вузлів (i, j), для яких не існує дуги, що з'єднує їх, приписується вартість .

Задача, що вирішується в даній роботі, полягає в знаходженні такого шляху з джерела s до стоку t, для якого вартість проходження одиниці потоку буде мінімальна.

Математично ця задача може бути записана так:

мінімізувати (1.3)

за умови, що

(1.4)

(1.5)

(1.6)

(1.7)

Згідно з обмеженням (1.4), одиниця потоку витікає з джерела. Рівняння (1.5) гарантує збереження даної одиниці потоку при проходженні в мережі. Згідно з рівнянням (1.6), одиниця потоку потрапляє до стоку. В якості найкоротшого шляху може бути взята послідовність суміжних дуг , для яких . Для розв’язання цієї типової задачі лінійного програмування скористуємось спеціальним засобом, відомим під назвою алгоритм Дейкстри [3].

Алгоритм базується на приписуванні вузлам тимчасових, або постійних позначок. Спочатку кожному вузлу, окрім джерела, приписується тимчасова позначка, яка дорівнює довжині найкоротшої дуги, що веде з джерела в даний вузол. Джерелу приписується постійна позначка, значення якої дорівнює нулю. Кожному вузлу, у який не можна потрапити безпосередньо з джерела, приписується тимчасова позначка , а всім іншим вузлам - тимчасові позначки . Якщо визначено, що вузол належить до найкоротшого шляху, його позначка стає постійною. Алгоритм базується на наступному простому факті: якщо відомий найкоротший шлях з вузла s у вузол та вузол належить до цього шляху, то найкоротший шлях з s до є частиною першого шляху, що закінчується в вузлі . Алгоритм починає працювати при . Після цього величина послідовно збільшується на одиницю і при алгоритм завершує роботу.