Знаходження найкоротших шляхів в графі методом Шімбелла

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

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

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

Отже, нехай дано деякий орієнтований зважений граф , який не містить петель. Матриця суміжності даного графа має розмірність , де  — кількість його вершин. За номера рядків матриці приймають ті вершини, з яких ребра виходять (початкова вершина ребра), за номери стовпців — вершини, в які ребра входять (кінцева вершина ребра). Елемент матриці , тобто елемент що знаходиться на перетині -го рядка та -го стовпця, означає довжину ребра . Якщо з вершини  в -у вершину орієнтоване ребро не входить, то відповідний елемент  матриці суміжності позначають нескінченністю. Діагональні елементи приймають значення, рівні нулю.

Орієнтований граф та його матриця суміжності

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

1. Операція множення двох величин і при піднесенні матриці в степінь відповідає їх алгебраїчній сумі, тобто відповідає . До прикладу відповідає .
2. Добуток нескінченності на будь-яке число дорівнює нескінченності .
3. Сума двох величин дорівнює мінімальному з доданків, тобто  відповідає . Наприклад відповідає .

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

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

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

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

Знаходження найкоротших шляхів в графі методом Шімбелла — приклад:

Для графа зображеного на рисунку нижче, визначити найкоротший шлях від вершини номер «1» до вершини «4».

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

Отже, на першому кроці, для заданого графа, будуємо матрицю суміжності:

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

Аналогічним чином розраховуємо елементи матриць і :

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

Далі, переходимо до визначення наступної ланки шляху та вузла . Для цього, знову-таки, складаємо аналогічну рівність, де замість вузла записується вузол  (), згідно з якою отримаємо, що .

Найкоротший шлях між двома вершинами графа отриманий за методом Шімбелла

Зазначимо, що виходячи з того, що вузол номер «2» поєднаний орієнтованим ребром з початковою вершиною, то, згідно з алгоритмом методу Шімбелла, найкоротший шлях знайдений і складається з наступних вузлів: .

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

Блок-схема алгоритму знаходження найкоротших шляхів в графі методом Шімбелла