Рішення задачі про найкоротший маршрут методом Форда
1. Постановка мережевий транспортної задачі.

На практиці часто зустрічається задача визначення найкоротшого маршруту по
заданої мережі з початкового пункту до кінцевого пункту маршруту. Транспортна
мережа може бути представлена у вигляді графа (рис. 1), дуги якого - транспортні
магістралі, а вузли - пункти відправлення та призначення. Графічно транспортна
мережа зображується у вигляді сукупності n пунктів P1, P2 ,..., Pn, причому деякі
впорядковані пари (Pi, Pj) пунктів призначення з'єднані дугами заданої довжини
r (Pi, Pj) = lij. Деякі чи всі дуги можуть бути орієнтовані, тобто по них
можливий рух тільки в одному напрямку, зазначеному стрілками.
На рис.1 побудована орієнтована транспортна мережа, що містить шість пунктів
P1, P2 ,..., P6, які пов'язані між собою вісьмома транспортними шляхами.
Необхідно визначити найкоротший маршрут з пункту P1 в P6. Визначення
найкоротшого маршруту полягає у вказівці послідовності проходження маршруту
через точки, і сумарної довжини маршруту.
Наприклад маршрут з пункту P1 в пункт P6: P1P2P4P6; L = l12 + l24 + l46 = 10.
Постановка завдання набуває сенсу в тому випадку, якщо є декілька
варіантів маршруту з початкового пункту в кінцевий. У цьому випадку фізичний
сенс функції мети завдання полягає в мінімізації загальної довжини маршруту, тобто в
визначенні найкоротшого шляху з P1 в Pn.
2. Опис методу і алгоритму рішення.
Метод Форда бал розроблений спеціально для вирішення мережевих транспортних задач і
заснований, по суті, на принципі оптимальності.
Алгоритм методу Форда містить чотири етапи (схема 1). На першому етапі
проводиться заповнення вихідної таблиці відстаней від будь-якого i-го пункту в
будь-який інший j-й пункт призначення. На другому етапі визначаються для кожного
пункту деякі параметри li і lj за відповідними формулами. Далі на третьому
етапі визначаються найкоротші відстані. Нарешті, на четвертому етапі
визначаються найкоротші маршрути з пункту відправлення Р1 в будь-який інший пункт
призначення Рj, j = 1,2 ,..., n.
Розглянемо докладніше кожний з цих чотирьох етапів.
2.1 Перший етап: Складання вихідної таблиці відстаней.
Дана таблиця містить n +1 рядків і така ж кількість шпальт; Pi - пункти
відправлення; Pj - пункти призначення. У другому рядку і другий стовпці
проставляється значення параметрів li іlj, визначення значень яких
виробляються на другому етапі рішення задачі. В інших клітинах таблиці
проставляються значення відстаней lij з i-го пункту в j-й пункт. Причому
заповнюємо клітини таблиці, що лежать вище головної діагоналі. Якщо пункт Pi не
з'єднаний відрізком шляху до пункту Pj, то відповідна клітка таблиці не
заповнюється.
2.2 Другий етап: Визначення li і lj.
Визначається значення параметрів відповідно до формули:
lj = min (li + lij); i = 1,2 ,..., n; j = 1,2 ,..., n, (1)
де l1 = 0.
Ці значення заповнюються в другому рядку і в другому стовпчику.
2.3 Третій етап: Визначення довжини найкоротших шляхів.
Можливі два випадки визначення довжини найкоротших шляхів з пунктів Pi в пункти
Pj, i = 1,2 ,..., n; j = 1,2 ,..., n.
У першому випадку, якщо виконуються нерівність:
lj - li