Page 87 - 2589

Проте для складних графів має бути знайдений систематичний
метод.

Загальне правило для знаходження найкоротшого шляху в

графі полягає в тому, щоб кожній вершині x приписати індекс
i
 рівний довжині найкоротшого шляху з цієї вершини в кінцеву.
i
Приписування індексів вершинам у разі графа з ребрами

одиничної довжини робиться в наступному порядку:
1) кінцевій вершині x приписується індекс 0;
0
2) всім вершинам, з яких виходить ребро в кінцеву
вершину, приписується індекс 1;

3) усім вершинам, що ще не мають індексів, з яких йде
ребро у вершину з індексом  , приписується індекс  +1. Цей
i i
процес триває до тих пір, поки не буде помічена початкова
вершина. Після закінчення розмітки індекс у початкової вершини
дорівнюватиме довжині найкоротшого шляху. Сам найкоротший

шлях знайдемо, якщо рухатимемося з початкової вершини у
напрямі спадання індексів.
Приклад розмітки індексів і визначення найкоротшого шляху

показаний на рис.4.6,в для m = 3.
Відмітимо, що описаний спосіб визначення найкоротшого
шляху є частковим випадком знаходження оптимального

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

5.7.3 Знаходження найкоротшого шляху в графі з
ребрами довільної довжини

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

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

зірочкою, в кінцеву вершину має довжину (ul )  12 , тоді як
обхідний шлях через вершину, відмічену трикутником, має

довжину. (ul )  10 .

Процес приписування індексів для такого виду графів
полягає в наступному:

87