Знаходження найкоротших шляхів в графі методом Шімбелла
Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів в графі останнім часом інстенсівно розвивається і використовується в різних сферах діяльності, наприклад, для знаходження оптимального матршрута між двома об'єктами на місцевості (найкоротший шлях від будинку до університету), для знаходження оптимального матршрута при перевезеннях, в системах автопілота, в системах комутації інформаційних пакетів в мережі Internet тощо. Найбільш поширені методи визначення зазначених шляхів діляться на дві категорії. Це індексні та матричні методи.
В основу індексних методів покладено принцип індексації, тобто принцип присвоєння вершинам графа деяких індексів, значення яких змінюються в процесі вирішення. Ці величини в результаті реалізації алгоритму визначають довжину шляху від вихідної до заданої вершини. До індексних методів належать методи Дейкстри, метод Беллмана-Форда, метод Мура та інші.
Всі ж матричні методи пов'язані з побудовою матриці суміжності, елементами якої є довжини відповідних ребер графа. Найкоротші шляхи, в даному випадку, знаходяться послідовним перетворенням цієї матриці. До цих методів належить розглядуваний нижче метод Шімбелла та метод Оттермана.
Отже, нехай дано деякий орієнтований зважений граф , який не містить петель. Матриця суміжності
даного графа має розмірність
, де
— кількість його вершин. За номера рядків матриці приймають ті вершини, з яких ребра виходять (початкова вершина ребра), за номери стовпців — вершини, в які ребра входять (кінцева вершина ребра). Елемент
матриці
, тобто елемент що знаходиться на перетині
-го рядка та
-го стовпця, означає довжину ребра
. Якщо з вершини
в
-у вершину орієнтоване ребро не входить, то відповідний елемент
матриці суміжності позначають нескінченністю. Діагональні елементи приймають значення, рівні нулю.
Орієнтований граф та його матриця суміжності
Для знаходження найкоротшого шляху між будь-якими двома вершинами А. Шімбеллом був розроблений метод, що використовує спеціальні операції над елементами вихідної матриці:
- Операція множення двох величин
і
при піднесенні матриці в степінь відповідає їх алгебраїчній сумі, тобто
відповідає
. До прикладу
відповідає
.
- Добуток нескінченності на будь-яке число дорівнює нескінченності
.
- Сума двох величин дорівнює мінімальному з доданків, тобто
відповідає
. Наприклад
відповідає
.
За допомогою зазначених операцій довжини найкоротших шляхів між усіма вершинами графа визначаються за допомогою піднесення матриці суміжності до степені. До прикладу, елементи матриці обчислюються наступним чином:
і визначають довжини найкоротших шляхів, що складаються не більше ніж з ребер. Оскільки шлях, що проходить через всі вершини графа і складається з максимальної кількості ланок, матиме не більше
ребер, то для отримання мінімального шляху між будь-якими двома вершинами вказаний процес отримання елементів потрібно провести не більше
раз.
Якщо в процесі множення виявиться, що , то подальше множення матриць припиняється, а величина
визначає максимальне число ребер в найкоротшому шляху між будь-якою парою вершин. Для визначення самого мінімального шляху використовуються матриці
і
. Покажемо яким чином це реалізується. Отже, нехай необхідно знайти мінімальний шлях від вершини
до вершини
. Для цього, на першому кроці, визначається таке
, для якого виконується рівність
, де
і
вибирається з
. Тоді ребро
буде останньою ланкою, а вершина
передостаннім вузлом на цьому шляху.
Далі, переходимо до визначення наступної ланки шляху та вузла . Для цього, знову-таки, складається аналогічна рівність, де замість вузла
записується вузол
:
. Після знаходження
визначаємо
і так далі до тих пір, поки не знайдемо вузол
, суміжний з початковою вершиною
. Зазначимо, що в такому випадку, оптимальний шлях матиме вигляд
. Довжина цього шляху, при цьому, дорівнюватиме
.
Знаходження найкоротших шляхів в графі методом Шімбелла — приклад:
Для графа зображеного на рисунку нижче, визначити найкоротший шлях від вершини номер «1» до вершини «4».
Орієнтований граф
Отже, на першому кроці, для заданого графа, будуємо матрицю суміжності:
На наступному кроці, за методом Шімбелла, піднесемо матрицю до другої, третьої та четвертої степунці. Продемонструємо застосування правил множення матриць в методі Шімбелла на прикладі обчислення елементів матриці
:
Аналогічним чином розраховуємо елементи матриць і
:
Знайдемо тепер довжину оптимального маршруту між заданими вершин. Отже, з рівностей випливає, що мінімальним буде один із шляхів, що складаються з трьох ланок. Перейдемо до визначення цього мінімального шляху. Для цього, скориставшись елементами матриць
та
, на першому кроці, знайдемо таке
, для якого виконується рівність
, де
. В результаті отримаємо, що
, тобто ребро
є останньою ланкою, а вершина номер «5» останнім вузлом шуканого найкорготшого шляху.
Далі, переходимо до визначення наступної ланки шляху та вузла . Для цього, знову-таки, складаємо аналогічну рівність, де замість вузла
записується вузол
(
), згідно з якою отримаємо, що
.
Найкоротший шлях між двома вершинами графа отриманий за методом Шімбелла
Зазначимо, що виходячи з того, що вузол номер «2» поєднаний орієнтованим ребром з початковою вершиною, то, згідно з алгоритмом методу Шімбелла, найкоротший шлях знайдений і складається з наступних вузлів: .
Зауваження: при визначенні максимальних довжин маршрутів замість операції в алгоритмі Шімбелла необхідно використовувати аналогічну операцію
.