Алгоритми визначення найкоротших відстаней на графі

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

Сформулюємо завдання про найкоротший шлях. Нехай дано пов'язаний граф, що маєRвершин іNорієнтованих дуг, причому кожній дузі поставлено у відповідність невід'ємне числоCijзване її довжиною. Потрібно знайти на графі найкоротші шляхи та його довжини від заданої вершиниIoдо решти вершин цього графа. Під довжиною найкоротшого шляху у своїй мається на увазі сума довжин складових цей шлях дуг. У кожну вершину графа може входити лише одна дуга, що належить якомусь найкоротшому шляху.

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

Більшість цих алгоритмів можуть бути розбиті на дві групи.

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

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

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

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

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

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

На будь-якому етапі обчислень найкоротших відстаней від заданої вершини всі вершини мережі розбиваютьсяна три множини:

- множина 1 - вершини, найкоротші відстані до яких вже визначені;

- множина 2 - вершини сусідні (тобто пов'язані дугою) з вершинами, відстань до яких вже визначено;

- безліч 3 - всі інші вершини. Суть методу зводиться до наступного.

1. Вибирається початкова вершина мережі, відстань від якої до решти вершин необхідно визначити. Цій вершині присвоюють відстань, що дорівнює 0, решті вершинприсвоюють відстань, що дорівнюєМ(дуже велике число).

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

3. Процес повторюють до тих пір, поки всі вершини не будуть переведені в першу множину.

Джерело:Вантажні автомобільні перевезення: Навч. посібник для студ. вищ. навч. закладів / А. Е. Горьов. - 5-е вид., Випр. - М.: Видавничий центр «Академія», 2008. - С. 185-187 (288 с.)

• Диспетчерське керівництво перевезеннями – 16/06/2011 19:18

• Побудова моделі транспортної мережі - 16/06/2011 18:45

Останні новини на сайті

---