Кінцевий пункт

Рис. 3.2. Найкоротші маршрути у вузол 1

3.2. Найкоротший маршрут на ациклічній мережі

На попередньому кроці пронумеруємо вузли мережі від 1 до p таким чином, що, якщо мережа містить дугу (i, j), то i > j. Щоб домогтися виконання цієї умови, привласнимо стокові або кінцевому вузлу, тобто вузлу, що не має вихідних дуг, номер 1. Закреслимо цей вузол та усі вхідні до нього дуги і не будемо їх розглядати надалі при присвоєнні номерів. Візьмемо будь-який інший вузол, що має тепер тільки вхідні до нього дуги, й припишемо йому номер 2. Закреслимо цей вузол та всі вхідні до нього дуги і виключимо їх з розгляду при подальшому присвоєнні номерів. Будемо продовжувати цей процес доти, поки усі вузли не будуть пронумеровані. Значення величин у_i будемо визначати у порядку нумерації вузлів.

Алгоритм складається з двох кроків

y₁ = 0 (кінцевий вузол), (3.10)

у_i = min (c_ij + y_i) при i = 2, 3, ..., р. (3.11)

(i, j)  мережі

Кінцевий пункт

Рис. 3.3. Приклад задачі про найкоротший маршрут на ациклічній мережі

Для з’ясування роботи алгоритму, точніше рекурентного співвідношення (3.11), розглянемо мережу, приведену на рис. 3.3, де величини с_ij поставлені біля кожної дуги. (Пронумеруйте вузли самостійно за викладеним вище правилом, щоб переконатися, що нумерація на рисунку відповідає умові i > j.) У результаті використання даного алгоритму одержуємо:

y₁ = 0,

y₂ = min (c₂₁ + y₁) = min (1 + 0) = 1,

y₃ = min (c₃₁ + y₁, c₃₂ + y₂) = min (4 + 0, 1 + 1) = 2,

y₄ = min (c₄₁ + y₁, c₄₃ + y₃) = min (4 + 0, 1 + 2) = 3,

y₅ = min (c₅₁ + y₁, c₅₄ + y₄) = min (6 + 0, 2 + 3) = 5,

y₆ = min (c₆₁ + y₄, c₆₅ + y₅) = min (3 + 3, 2 + 5) = 6,

y₇ = min (c₇₂ + y₂, c₇₃ + y₃, c₇₆ + y₆) = min (8 + 1, 6 + 2, 1 + 6) = 7,

y₈ = min (c₈₅ + y₅, c₈₆ + y₆, c₈₇ + y₇) = min (6 + 5, 4 + 6, 1 + 7) = 8.

Рис. 3.4. Найкоротші маршрути в ациклічній мережі

Як і в попередньому розділі, обчислення можна виконувати безпосередньо на кресленні. Маршрути також визначаються, як і раніше. Отримане в даному прикладі рішення показане на рис. 3.4.

3.3. Mаксимальний потік у мережі з обмеженими пропускними здатностями

Для розробки ефективних методів рішення для складних мережних моделей найважливішу роль відіграє наступна задача: якою є максимальна величина потоку з джерела у вихід для заданої мережі з обмеженими пропускними здатностями дуг, у якої вузол 0 є єдиним джерелом, а вузол є єдиним виходом? Математично задача формулюється у такий спосіб:

максимізувати F (3.12)

при обмеженнях

(3.13)

(3.14)

(3.15)

(3.16)

де u_ij – ненегативні цілі числа.

Для рішення цієї задачі можна використовувати досить простий метод. Щоб основна ідея алгоритму стала зрозумілою, приймемо

(3.17)

Якщо освоїти метод рішення даної задачі за умови (3.17), то не виникне ніяких труднощів у розумінні модифікації алгоритму, котра вимагається для відшукання рішення у загальному випадку.

Почнемо з будь-якого припустимого потоку. Чи є потік максимальним або можливим є його подальше збільшення, можна визначити у такий спосіб:

Крок 1. Починаючи з вузла 0, поставити знак + на кожній дузі (0, j) з нульовим потоком, а вузол j позначити знаком \/. Вузол 0 позначити знаком \/.

Крок 2. Розглянути будь-який вузол j, позначений знайомий \/. Поставити знак + на кожній дузі (j, k) з нульовим потоком, що виходить з вузла j, якщо вузол k не позначений, і позначити вузол k знаком \/. Потім проставити знак – на кожній дузі (k, j) з ненульовим потоком, що входить у вузол j, якщо вузол k не позначений, і позначити вузол k знаком \/. Наприкінці кроку 2 закреслити знак \/ у вузла j, що вказує на те, що цей вузол був також переглянутий.

Крок. 3. Повторювати операції кроку 2, поки не буде позначені вузол або всі позначені вузли не будуть переглянуті. Як тільки проставляється позначка біля вузла , відбувається прорив, тому що при цьому виявляється шлях, що збільшує потік, з вузла 0 у вузол . Цей шлях можна виявити в явному виді за допомогою знаків + або –, проставлених на дугах, переглядаючи вузли в зворотному напрямку, починаючи з вузла . Додати одиничний потік по кожній дузі, позначеної знаком +, і зменшити на одиницю потік по кожній дузі, позначеної знаком –. Повернутися до кроку 1. Однак, якщо по закінченні кроку 2 вузол залишається непоміченим, поточне рішення визначає максимальний потік у мережі.

Робота алгоритму ілюструється на прикладі, приведеному на рис. 3.5.