Довжина найкоротшого шляху дорівнює .... Рухаючись від початкової вершини до кінцевої по виділеним ребрах, отримаємо найкоротший шлях.
3. Завдання визначення максимального потоку
Розглядається мережу з одним вузлом входу (джерело) і одним вузлом виходу (стік). Визначити максимальну величину потоку (кількість машин, повідомлень, рідини і т.д.), який може увійти в мережеву систему і вийти з неї в заданий період часу. Передбачається, що потік, що випливає з вузла, дорівнює потоку, що впадає в вузол.
Пропускна здатність (або потужність) дуги - верхнє обмеження на потік в цій дузі. Наприклад, автомобільні траси обмежують число автомобілів в транспортній системі, величина трубопроводів обмежує кількість нафти в системі її розподілу.
Потужність потоку може залежати від його напряму.
Це умовне позначення означає, що потужність потоку від вузла 1 до вузла 2 дорівнює 6, а потужність потоку від вузла 2 до вузла 1 дорівнює 0, тобто це «вулиця з одностороннім рухом».
означає, що потужність потоку в кожному напрямку дорівнює 2.
Вважаємо шукану величину максимального потоку рівною нулю.
Крок 1. Знайти який-небудь шлях від джерела до стоку, який утворений дугами, кожна з яких має в напрямку потоку ненулевую потужність. Якщо такого шляху немає, то оптимальне рішення знайдено.
Крок 2. Знайти найменше значення потужності дуги Pf на обраному шляху кроку 1. Збільшити потік через мережу на величину Pf.
Крок 3. На шляху з кроку 1 скоротити на Pf потужності потоків на всіх дугах в напрямку потоку і збільшити на Pf потужності потоків на всіх дугах, в зворотному напрямку. Перейти до кроку 1.
Приклад. Система автодоріг «Північ-Південь», що проходять через Псковську область, може забезпечити пропускні спроможності, показані на схемі (тис. Автомашин в годину).
Визначити максимальний потік через цю систему (тис. Автомашин в годину).
Шукану величину максимального потоку покладемо рівною нулю.
Ітерація 1. Виберемо шлях
Pf = min = .... Тому потужності потоків на шляху ......... в напрямку потоку (а саме, ... і ...) зменшуємо на величину Pf = ..., а потужності потоків в зворотному напрямку на шляху .......... (... і ...) збільшуємо на Pf = .... Загальний потік стане
Ітерація 2. Виберемо шлях
Pf = min = .... Всі потоки на шляху ......... в напрямку загального потоку (... і ...) зменшуємо на Pf = ..., а все потоки на цьому шляху в зворотному напрямку (... і ...) збільшуємо на Pf = .... Загальний потік збільшуємо на Pf = ... (............).
Ітерація 3. Вибираємо шлях
Pf = min = .... Всі потоки на шляху .......... в напрямку загального потоку (.............) зменшуємо на Pf = ..., а все потоки на цьому шляху в зворотному напрямку (............) збільшуємо на Pf = .... Загальний потік збільшуємо на Pf = ... (................).
Ітерація 4. Вибираємо шлях
Pf = min = .... Всі потоки на шляху ................ в напрямку загального потоку (............... ..) зменшуємо на Pf = ..., а все потоки на цьому шляху в зворотному напрямку (............... ..) збільшуємо на Pf = .... Загальний потік збільшуємо на Pf = ... (............ ..).
Ітерація 5. Вибираємо шлях
Pf = min = .... Всі потоки на шляху ................... в напрямку загального потоку (.................. ..) зменшуємо на Pf = ..., а все потоки на цьому шляху в зворотному напрямку (.................. ..) збільшуємо на Pf = .... Загальний потік збільшуємо на Pf = ... (.............).
Більше не існує шляхів з вузла 1 до вузла 6 з потужністю, що перевищує нуль на всьому шляху. Отже, .... тис. - це максимальний потік через мережу.
Визначимо величину і напрям потоку на кожній дузі. Напрямок потоків відповідає обраним шляхах. Потік проходить по дузі з величиною, що дорівнює різниці між первісною і кінцевої потужностями потоку:
дуга 1-2: первісна потужність дорівнює ... (у вихідному графі), кінцева - ... (в останньому графі), отже, в напрямку від вузла 1 до вузла 2 потік має потужність
В результаті отримаємо граф, на якому вказані напрямки і потужності потоків по кожній дузі: