Рішення задачі про найкоротший маршрут методом Форда

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-й пункт призначення. На другому етапі визначаються для кожного пункту деякі параметри l i і l j за відповідними формулами. Далі на третьому етапі визначаються найкоротші відстані. Нарешті, на четвертому етапі визначаються найкоротші маршрути з пункту відправлення Р1 в будь-який інший пункт призначення Рj, j = 1,2 ,..., n.

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

2.1 Перший етап: Складання вихідної таблиці відстаней.

Дана таблиця містить n +1 рядків і така ж кількість шпальт; Pi - пункти відправлення; Pj - пункти призначення. У другому рядку і другому стовпчику проставляється значення параметрів l i іl j, визначення значень яких виробляються на другому етапі рішення задачі. В інших клітинах таблиці проставляються значення відстаней lij з i-го пункту в j-й пункт. Причому заповнюємо клітини таблиці, що лежать вище головної діагоналі. Якщо пункт Pi не з'єднаний відрізком шляху до пункту Pj, то відповідна клітка таблиці не заповнюється.

2.2 Другий етап: Визначення l i і l j.

Визначається значення параметрів відповідно до формули:

l j = min (l i + lij); i = 1,2 ,..., n; j = 1,2 ,..., n, (1)

де l 1 = 0.

Ці значення заповнюються в другому рядку і в другому стовпчику.

2.3 Третій етап: Визначення довжини найкоротших шляхів.

Можливі два випадки визначення довжини найкоротших шляхів з пунктів Pi в пункти Pj, i = 1,2 ,..., n; j = 1,2 ,..., n.

У першому випадку, якщо виконуються нерівність:

l j - l i