Лекція 08. Мережеві моделі: найкоротший шлях, потоки та мінімальна вартість

Коротко про лекцію

Лекція вводить граф як природну модель доріг, каналів і маршрутів. Ви розрізните задачу найкоротшого шляху та задачу потоку, навчитеся враховувати пропускні здатності, баланс у вузлах і вартість перевезення.

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

Постановка та базові поняття

1. Коли задача природно є мережею

Багато прикладних систем уже мають мережеву структуру. Міста з’єднані дорогами. Сервери з’єднані каналами. Склади передають вантаж через проміжні вузли.

У таких задачах важливо зберегти числові коефіцієнти разом зі структурою зв’язків. Граф робить цю структуру явною.

1.1. Навіщо мережеву задачу перетворювати на граф

Коли об’єкти з’єднані дорогами, каналами, кабелями або маршрутами, таблиця коефіцієнтів приховує саму структуру зв’язків. Граф робить її явною: вершини представляють об’єкти, а ребра — можливі переходи між ними.

Для маршруту важлива послідовність ребер. Таку послідовність називають шляхом. Для задач перевезення або передачі даних на ребрі з’являється потік — кількість ресурсу, що проходить цим зв’язком. Пропускна здатність задає найбільший дозволений потік через ребро.

Тому мережеві терміни описують прикладну структуру, а не додають назви заради назв. Вони стискають повторювані ситуації в кілька стандартних об’єктів, для яких існують спеціалізовані алгоритми.

2. Що таке граф

Граф записують як:

\[ G=(V,E) \]

\(V\) — множина вершин. \(E\) — множина ребер або дуг.

Для нашого прикладу:

\[ V=\{A,B,C,D,E\} \]

Вершини можуть означати міста або логістичні вузли.

3. Орієнтований та неорієнтований граф

У неорієнтованому графі ребро \(A-B\) дозволяє рух в обидва боки.

В орієнтованому графі дуга \(A\to B\) задає конкретний напрям.

Напрям потрібно вибирати за предметним змістом. Одностороння дорога, виробничий потік або передача даних часто потребують орієнтованої мережі.

4. Вага ребра

Кожне ребро може мати числову вагу \(w_{uv}\).

Вага може означати:

1. відстань;
2. час;
3. вартість;
4. ризик;
5. споживання ресурсу.

Для задачі найкоротшого шляху ми мінімізуємо суму ваг уздовж маршруту.

5. Наскрізна мережа

Використаємо такі ребра:

Ребро	Вага
\(A-B\)	4
\(A-C\)	2
\(C-B\)	1
\(B-D\)	5
\(C-D\)	7
\(B-E\)	9
\(C-E\)	12
\(D-E\)	2

Потрібно знайти найдешевший шлях від \(A\) до \(E\).

6. Що називають шляхом

Шлях — послідовність суміжних вершин.

Наприклад:

\[ A\to C\to B\to D\to E \]

Його вартість дорівнює сумі ваг:

\[ 2+1+5+2=10 \]

Інший шлях:

\[ A\to B\to E \]

має вартість:

\[ 4+9=13 \]

Тому другий маршрут гірший за перший.

Математична логіка

7. Формальна задача найкоротшого шляху

Нехай шлях \(P\) складається з множини використаних ребер.

Його вартість:

\[ L(P)=\sum_{e\in P}w_e \]

Потрібно знайти:

\[ P^*=\arg\min_P L(P) \]

Обмеження на \(P\) задає мережа: шлях повинен починатися у джерелі, завершуватися у цілі та рухатися тільки наявними ребрами.

8. Чому найдешевше сусіднє ребро не гарантує найкращий маршрут

У вершині \(A\) найдешевше ребро веде до \(C\) з вагою 2. У нашому прикладі цей вибір входить в оптимальний шлях.

Таке співпадіння не утворює загального правила. Локально дешевий крок може привести до дуже дорогого продовження.

Тому алгоритм повинен порівнювати накопичену вартість до вершин, а не тільки ціну останнього ребра.

9. Ідея алгоритму Дейкстри

Для графа з невід’ємними вагами алгоритм Дейкстри поступово фіксує найменші відомі відстані від джерела.

Для кожної вершини зберігається мітка \(d(v)\).

На старті:

\[ d(A)=0 \]

Для інших вершин:

\[ d(v)=\infty \]

На кожному кроці вибирається ще не зафіксована вершина з найменшою міткою. Потім перевіряються її сусіди.

10. Що означає релаксація ребра

Нехай ми вже маємо відстань \(d(u)\) до вершини \(u\). Ребро \(u\to v\) має вагу \(w_{uv}\).

Новий кандидат для \(v\):

\[ d(u)+w_{uv} \]

Мітка оновлюється правилом:

\[ d(v)=\min\left(d(v),d(u)+w_{uv}\right) \]

Цю операцію називають релаксацією ребра.

11. Ручний прохід для нашої мережі

Старт:

\[ d(A)=0 \]

Після перегляду сусідів \(A\):

\[ d(B)=4,\qquad d(C)=2 \]

Фіксуємо \(C\), бо 2 — найменша мітка.

Через \(C\to B\):

\[ 2+1=3<4 \]

Тому:

\[ d(B)=3 \]

Через \(C\to D\):

\[ d(D)=2+7=9 \]

Через \(C\to E\):

\[ d(E)=2+12=14 \]

Далі фіксуємо \(B\) з міткою 3.

Через \(B\to D\):

\[ 3+5=8<9 \]

Тому:

\[ d(D)=8 \]

Через \(B\to E\):

\[ 3+9=12<14 \]

Тому:

\[ d(E)=12 \]

Фіксуємо \(D\) з міткою 8.

Через \(D\to E\):

\[ 8+2=10<12 \]

Отримуємо:

\[ d(E)=10 \]

Найкоротший шлях:

\[ A\to C\to B\to D\to E \]

12. Як відновлюється сам маршрут

Одних відстаней недостатньо для відновлення послідовності вершин.

Під час кожного успішного оновлення зберігають попередника вершини.

Для оптимального шляху маємо:

\[ \operatorname{pred}(E)=D \]

\[ \operatorname{pred}(D)=B \]

\[ \operatorname{pred}(B)=C \]

\[ \operatorname{pred}(C)=A \]

Читання у зворотному порядку повертає маршрут від \(A\) до \(E\).

13. Від шляху до потоку

Найкоротший шлях відповідає на питання про одну траєкторію.

Якщо потрібно передати багато одиниць товару, з’являються потоки \(f_{uv}\) на дугах.

Кожна дуга може мати пропускну здатність:

\[ 0\le f_{uv}\le u_{uv} \]

Тут \(u_{uv}\) — максимальна допустима кількість потоку.

14. Закон збереження потоку

У проміжній вершині кількість потоку, що входить, повинна дорівнювати кількості потоку, що виходить.

Для вершини \(v\):

\[ \sum_{u} f_{uv}-\sum_{w}f_{vw}=0 \]

Джерело створює заданий обсяг потоку. Стік поглинає його.

Це мережевий аналог транспортних балансів попередньої лекції.

15. Мінімальна вартість потоку

Якщо кожна дуга має ціну \(c_{uv}\) за одиницю потоку, загальна вартість:

\[ C(f)=\sum_{(u,v)\in E}c_{uv}f_{uv} \]

Потрібно знайти допустимий потік з мінімальною вартістю:

\[ \min_f C(f) \]

Для 5 одиниць потоку від \(A\) до \(E\) і достатніх пропускних здатностей весь потік піде найдешевшим маршрутом.

Тоді:

\[ C=5\cdot10=50 \]

16. Зв’язок із транспортною задачею

Транспортна задача має два шари вузлів: постачальники й споживачі.

Потік мінімальної вартості допускає проміжні вершини, довільну мережу та пропускні здатності дуг.

Тому транспортну модель можна розглядати як спеціальний випадок задачі мінімальної вартості потоку.

Алгоритм і покроковий розбір

17. Послідовність перевірки найкоротшого шляху

Після отримання маршруту потрібно перевірити:

1. перша вершина збігається з джерелом;
2. остання вершина збігається з ціллю;
3. кожна сусідня пара є ребром графа;
4. сума ваг уздовж маршруту дорівнює заявленій довжині;
5. за потреби результат порівнюється з незалежним алгоритмом або ручними мітками.

Ця перевірка важлива, бо список вершин і числова довжина є двома пов’язаними результатами.

18. Візуальна історія міток Дейкстри

Графік показує, як кандидатна відстань до \(E\) зменшується від 14 до 12, а потім до 10.

Програмна реалізація та перевірка

19. Найкоротший шлях у NetworkX

NetworkX зберігає граф і ваги ребер у природній структурі.

# Імпортуємо NetworkX для обчислень, розв’язання моделі та її перевірки.
import networkx as nx


# Будуємо зважений граф: ваги ребер точно повторюють дані з постановки задачі.
graph = nx.Graph()

# Будуємо зважений граф: ваги ребер точно повторюють дані з постановки задачі.
graph.add_weighted_edges_from([
    ("A", "B", 4),
    ("A", "C", 2),
    ("C", "B", 1),
    ("B", "D", 5),
    ("C", "D", 7),
    ("B", "E", 9),
    ("C", "E", 12),
    ("D", "E", 2),
])

# Знаходимо найкоротший шлях за вагами ребер; його довжину далі перевіримо незалежно.
path = nx.shortest_path(
    graph,
    source="A",
    target="E",
    weight="weight",
)

# Знаходимо найкоротший шлях за вагами ребер; його довжину далі перевіримо незалежно.
length = nx.shortest_path_length(
    graph,
    source="A",
    target="E",
    weight="weight",
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Шлях:", path)
print("Вартість:", length)

Очікувано:

Шлях: ['A', 'C', 'B', 'D', 'E']
Вартість: 10

20. Незалежне повторне обчислення довжини

Після бібліотечного виклику варто повторно пройти шлях:

# Виконуємо операцію з графом і зберігаємо результат для незалежної перевірки.
verified_length = 0

# Перебираємо вибрані тестові значення, щоб порівняти поведінку методу на кількох випадках.
for start, end in zip(
    path,
    path[1:],
):
    verified_length += graph[start][end]["weight"]

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Перевірена вартість:", verified_length)

Очікуємо 10.

21. Потік мінімальної вартості в OR-Tools

Для потокової задачі OR-Tools надає SimpleMinCostFlow.

Модель потребує дуг, пропускних здатностей, вартостей і балансів вузлів.

У найпростішому випадку джерело має постачання \(+5\), стік має попит \(-5\), а проміжні вузли мають нульовий баланс.

CP або MIP-модель тут не потрібна, бо спеціалізований потоковий чисельний розв’язувач використовує структуру мережі безпосередньо.

22. Як перевіряти потік мінімальної вартості

Для кожної дуги перевіряємо межі змінних:

\[ 0\le f_{uv}\le u_{uv} \]

Для проміжних вершин перевіряємо баланс нуль.

Для джерела та стоку перевіряємо задані постачання/попит.

Потім повторно обчислюємо:

\[ \sum c_{uv}f_{uv} \]

Інтерпретація, межі та підсумок

23. Однакова довжина кількох шляхів

Найкоротший шлях може бути неунікальним.

Бібліотека може повернути один із кількох маршрутів з однаковою оптимальною довжиною.

Тому автоматична перевірка повинна оцінювати допустимість маршруту та його сумарну вагу. Порівняння тільки зі списком вершин може помилково відхилити інший оптимальний шлях.

24. Від’ємні ваги

Алгоритм Дейкстри розрахований на невід’ємні ваги.

Якщо граф має від’ємні ребра, потрібен інший алгоритм, наприклад Bellman–Ford. Від’ємні цикли можуть зробити задачу найкоротшого шляху некоректною для звичайного поняття мінімуму.

Перед вибором алгоритму перевірте семантику ваг і їхній допустимий діапазон.

25. Орієнтація ребер

У неорієнтованому графі ребро працює в обидва боки. У DiGraph напрям є частиною математичної моделі.

Помилка типу графа може створити маршрут, якого в реальній системі немає.

Тому перевірка графа починається ще до запуску алгоритму.

26. Типова помилка

Типова помилка. Після shortest_path перевіряють тільки число 10. Правильний аудит також перевіряє існування кожного ребра маршруту та повторно сумує його ваги.

26.1. Як подати граф у даних

Математичний граф потрібно перетворити на структуру даних. Для невеликої мережі зручно зберігати список ребер.

Кожний запис містить початкову вершину, кінцеву вершину та вагу. Наприклад:

\[ (A,C,2) \]

означає ребро між \(A\) і \(C\) з вагою 2.

Інший варіант — матриця суміжності. Для \(n\) вершин вона має розмір \(n\times n\). Елемент матриці показує наявність або вагу зв’язку між двома вершинами.

Для розріджених мереж список ребер або списки сусідів зазвичай природніші. Вони зберігають тільки наявні зв’язки.

26.2. Різниця між кількістю ребер і сумою ваг

У незваженому графі найкоротший шлях часто означає мінімальну кількість ребер.

У зваженому графі ми мінімізуємо суму ваг. Ці два критерії можуть давати різні маршрути.

У нашій мережі шлях:

\[ A\to B\to E \]

має два ребра, але вартість 13.

Шлях:

\[ A\to C\to B\to D\to E \]

має чотири ребра, але вартість 10.

Тому параметр weight у бібліотечному виклику є частиною математичної постановки.

26.3. Таблиця ручного алгоритму Дейкстри

Покроковий прохід можна звести в таблицю.

Фіксована вершина	\(d(B)\)	\(d(C)\)	\(d(D)\)	\(d(E)\)
старт \(A\)	4	2	\(\infty\)	\(\infty\)
після \(C\)	3	2	9	14
після \(B\)	3	2	8	12
після \(D\)	3	2	8	10
після \(E\)	3	2	8	10

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

26.4. Чому зафіксована мітка Дейкстри вже оптимальна

Ключове припущення — усі ваги невід’ємні.

Припустимо, вершина \(u\) має найменшу мітку серед усіх ще не зафіксованих вершин. Будь-який альтернативний шлях до \(u\) через іншу незавершену вершину повинен спочатку дійти до неї з відстанню не меншою за \(d(u)\).

Після цього потрібно додати ще невід’ємну вагу. Тому такий шлях не зможе зменшити \(d(u)\).

Ця логіка пояснює, чому від’ємне ребро руйнує передумову. Воно могло б пізніше зменшити вже зафіксовану мітку.

26.5. Попередник як частина результату

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

Коли \(d(B)\) змінюється з 4 на 3 через \(C\), записуємо:

\[ \operatorname{pred}(B)=C \]

Коли \(d(D)\) змінюється з 9 на 8 через \(B\):

\[ \operatorname{pred}(D)=B \]

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

26.6. Як перевірити шлях без NetworkX

Незалежна перевірка може використовувати простий словник ваг.

Для кожної пари сусідніх вершин \((v_k,v_{k+1})\) потрібно:

1. перевірити існування ребра;
2. взяти його вагу;
3. додати вагу до суми.

Математично:

\[ L(P)= \sum_{k=0}^{q-1} w_{v_kv_{k+1}} \]

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

Такий перевіряльник корисний у лабораторній роботі, бо він не залежить від того, який саме оптимальний шлях повернула бібліотека.

26.7. Що робити з кількома найкоротшими шляхами

Припустимо, два різні маршрути мають однакову суму ваг 10.

Тоді обидва є оптимальними. Перевірка через точний список вершин має ризик відхилити правильний альтернативний маршрут.

Надійний критерій складається з двох частин:

\[ P\text{ є допустимим шляхом} \]

і:

\[ L(P)=L^* \]

де \(L^*\) — відома оптимальна довжина.

Для чисел з плаваючою комою можна використовувати числовий допуск при порівнянні довжин.

26.8. Потік на тій самій мережі

Перетворимо ребра нашого прикладу на орієнтовані дуги від \(A\) у напрямку \(E\). Нехай кожна дуга має пропускна здатність не менше 5.

Джерело \(A\) повинно відправити 5 одиниць:

\[ b_A=5 \]

Стік \(E\) повинен отримати 5:

\[ b_E=-5 \]

Для проміжних вершин:

\[ b_B=b_C=b_D=0 \]

Якщо пропускні здатності не обмежують оптимальний маршрут, весь потік може пройти шляхом вартості 10.

Тоді сумарна вартість:

\[ 5\cdot10=50 \]

26.9. Чому один найкоротший шлях не завжди розв’язує потік-задачу

Припустимо, дуга \(C\to B\) має пропускна здатність 2, а потрібно передати 5 одиниць.

Тоді тільки 2 одиниці можуть пройти найдешевшим маршрутом через \(C\to B\). Решта потоку повинна використати інші дуги.

Задача вже не зводиться до множення «5 × довжина найкоротшого шляху».

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

26.10. Баланс вузла у знаковій формі

Для кожної вершини можна використати єдину формулу:

\[ \sum_{(v,w)\in E}f_{vw}-\sum_{(u,v)\in E}f_{uv}=b_v \]

Тут \(b_v>0\) означає постачання, \(b_v<0\) означає попит, а \(b_v=0\) — проміжний вузол.

Знакова домовленість може бути протилежною в іншій бібліотеці. Важливо зафіксувати її один раз і послідовно використовувати.

26.11. Вартість, пропускна здатність і потік — три різні числа

Для дуги \(u\to v\) корисно чітко розрізняти:

• \(c_{uv}\) — вартість однієї одиниці;
• \(u_{uv}\) — максимальна пропускна здатність;
• \(f_{uv}\) — фактичний потік.

У ціль входить добуток:

\[ c_{uv}f_{uv} \]

У обмеження входить:

\[ 0\le f_{uv}\le u_{uv} \]

Плутанина між цими величинами створює математично іншу мережеву задачу.

26.12. NetworkX і OR-Tools виконують різні ролі

NetworkX зручний для структури графа та алгоритмів шляхів. Він природно дозволяє зберігати вершини як рядкові мітки та ваги як атрибути ребер.

OR-Tools SimpleMinCostFlow орієнтований на потокову оптимізацію з пропускні здатності, одиничними вартостями та балансами постачання і попиту.

Вибір бібліотеки починається з математичного питання. Якщо потрібна одна траєкторія між двома вузлами, найкоротшого шляху API є природним. Якщо потрібно передати обсяг через мережу з пропускні здатності, потрібна потік-модель.

26.13. Мережевий результат як перевірюваний контракт

Для найкоротший шлях корисно зберігати:

PATH
PATH_LENGTH

Для потік мінімальної вартості:

STATUS
ARC_FLOWS
TOTAL_COST
MAX_CAPACITY_VIOLATION
MAX_FLOW_BALANCE_RESIDUAL

Такий формат змушує відокремити знайдені числа від перевірок.

Він також спрощує автоматичне оцінювання, бо перевіряльник може самостійно обчислити суму ваг або нев’язка баланси.

26.14. Вибір алгоритму за типом ваг

Перед запуском найкоротшого шляху чисельний розв’язувач потрібно класифікувати ваги. Для незваженої мережі достатньо рахувати кількість ребер. Для невід’ємних числових ваг природним базовим вибором є Дейкстра.

Якщо ваги можуть бути від’ємними, потрібен алгоритм, який допускає таку структуру. Від’ємний цикл потребує окремої діагностики, бо повторний обхід циклу може необмежено зменшувати вартість.

Тому вибір алгоритму починається з властивостей даних, а не з назви бібліотечної функції.

26.15. Відстань як функція від джерела

Алгоритм Дейкстри фактично будує цілу функцію:

\[ d_A(v) \]

яка задає найкоротшу відстань від \(A\) до кожної досяжної вершини \(v\).

У нашому прикладі:

\[ d_A(C)=2 \]

\[ d_A(B)=3 \]

\[ d_A(D)=8 \]

\[ d_A(E)=10 \]

Тому одна робота алгоритму може дати більше інформації, ніж тільки шлях до \(E\).

26.16. Недосяжна вершина

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

У такій ситуації бібліотека може повідомити про відсутність шлях. Це треба трактувати як властивість мережі, а не як звичайне числове значення.

Перед автоматичним обчисленням довжини корисно перевірити досяжність або коректно обробити відповідний статус бібліотеки.

26.17. Чому ваги мають одиниці вимірювання

Якщо вага означає хвилини, сума ваг шляху також вимірюється у хвилинах. Якщо вага означає гривні, результат має грошову одиницю.

Змішування часу й вартості в одному полі weight без попереднього нормування створює нечіткий критерій.

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

26.18. Перевірка напрямку у DiGraph

Для орієнтованої мережі маршрут \(A\to B\) не гарантує наявність \(B\to A\).

Тому перевіряльник повинен перевіряти конкретну впорядковану пару вершин. У математичному записі дуга є елементом:

\[ (u,v)\in E \]

Пара \((v,u)\) є окремою дугою і може бути відсутня.

26.19. Практична таблиця вибору моделі

Прикладна потреба	Математична модель	Типовий інструмент
найменша кількість переходів	незважений найкоротший шлях	NetworkX
мінімальна сума невід’ємних ваг	вагаed найкоротший шлях	NetworkX
потік з пропускні здатності	потік модель	OR-Tools
потік із одиниця вимірювання вартості	потік мінімальної вартості	OR-Tools
кілька дискретних логічних умов	цілочисельна модель	MILP або CP-SAT

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

26.20. Ручний аудит бібліотечного маршруту

Після отримання path студент повинен записати послідовність ребер і їхні ваги. Для нашого маршруту це \(A-C\), \(C-B\), \(B-D\), \(D-E\). Сума \(2+1+5+2\) дає 10. Якщо бібліотека повернула інший шлях з тією самою довжиною, він також може бути оптимальним.

26.21. Мережа як модель обмежень

Сам список ребер уже є частиною допустимої множини. Відсутнє ребро означає заборонений прямий перехід. Тому помилка в побудові графа змінює задачу ще до запуску найкоротшого шляху алгоритму. Перевірка даних графа є таким самим етапом моделювання, як перевірка матриці \(A\) у LP.

26.22. Як перевірити вхідні дані графа

Перед запуском найкоротшого шляху алгоритму варто перевірити сам граф. Усі вершини маршруту повинні існувати. Вага кожного ребра має бути числом із коректною предметною одиницею. Для Дейкстри окремо перевіряємо невід’ємність ваг.

Також потрібно перевірити дублікати ребер і напрям. У Graph повторне додавання тієї самої пари вершин може оновити атрибути, а в MultiGraph допускаються паралельні ребра. Тому тип структури даних повинен відповідати математичній моделі.

26.23. Короткий ручний сертифікат оптимального шляху

Для маленької мережі студент може подати фінальні мітки:

\[ d(A)=0,\quad d(C)=2,\quad d(B)=3,\quad d(D)=8,\quad d(E)=10 \]

і ланцюжок попередників:

\[ E\leftarrow D\leftarrow B\leftarrow C\leftarrow A \]

Ці два набори даних разом показують довжину та структуру маршруту. Після цього окреме підсумовування ваг дає незалежну числову перевірку.

26.24. Коли мережеву задачу краще записати як LP

Графовий алгоритм зручний, коли структура задачі точно відповідає найкоротший шлях або потік. Якщо з’являються додаткові глобальні обмеження, наприклад бюджет на групу ребер або логічна умова вибору маршруту, спеціалізованої моделі може бути недостатньо.

Тоді мережеву структуру можна вбудувати в LP або MILP. Вибір методу визначається повною системою обмежень, а не тільки наявністю графа.

26.25. Міні-чекліст мережевої задачі

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

Цей чекліст відділяє математичну правильність від конкретного порядку, у якому бібліотека повернула результат.

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

Також зафіксуйте одиниці ваг і напрям дуг. Без цього правильний алгоритм працюватиме з неправильною мережею.

Це завершує перевірку структури, маршруту та числової вартості.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

27. Підсумок

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

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

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