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

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

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

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

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

Метод Шімбелла

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

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

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

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

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

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

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

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

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

Метод Шімбелла приклад

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

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

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

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

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

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

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

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

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

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

Метод Шімбелла блок-схема

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар