бо, що те ж саме, за кількістю дуг, складових найкоротший шлях. Якщо це сталося на першому кроці (що можливо тільки у випадку, якщо початкова та кінцева вершини з'єднані дугою нульової довжини), то доказувана твердження очевидно. Припустимо, що воно вірно для всіх пунктів, позначених за перші r ітерацій, тобто тих, які досягаються переходом по r дуг. Тоді, якщо кінцева вершина t позначена на (r + 1)-ої ітерації, то отриманий шлях також буде найкоротшим, так як дана вершина позначається в результаті мінімально можливого продовження одного з шляхів, отриманого за попередні r ітерацій і є за припущенням найкоротшим.
Описаний алгоритм придатний для побудови найкоротших шляхів на неорієнтованих графах.
2. Алгоритмічне забезпечення
Розглянемо викладений метод на конкретному прикладі, а саме: визначимо найкоротший шлях з вершини 1 у вершину 6 для неориентированной мережі, показаної на малюнку 1.
В
Рисунок 1 - неорієнтована мережа із заданими довжинами дуг для знаходження найкоротшого шляху
На попередньому етапі вершина 1 зазначається числом m1 = 0, а модифіковані довжини збігаються із заданими довжинами дуг.
Ітерація 1. Так як з вершини 1 не виходять дуги нульової довжини, подальша відмітка вершин неможлива. Переходимо до етапу 2. Суміжними з вершиною 1 є вершини 2 і 3. Для них визначаємо? = Min { 1,2, 1,3} = 2 і віднімаємо її з 1 , 2, 1,3. Після перетворення маємо 1,2 = 0, 1,3 = 1. Результати можна побачити на малюнку 2.
В
Рисунок 2 - Змінена мережу після виконання першої ітерації
Ітерація 2. Позначаємо вершину 2 m2 = 1 (див. малюнок 3). Подальша позначка неможлива, тому переходимо до етапу 2. Суміжними з позначеними вершинами 1 і 2 є вершини 3,4,5. З чого визначаємо? = Min { 1,3, 2,3, 2,4, 2,5} = 1 і після відповідного перетворення маємо
В
Рисунок 3 - Змінена мережу після виконання другої ітерації
Ітерація 3. У вершину 3 ведуть дуги нульової довжини як з вершини 1, так і з вершини 2. Оскільки вибір тут може бути довільним, пометим вершину 3 числом m3 = 1 (малюнок 4). Подальша позначка неможлива, тому переходимо до етапу 2. Суміжними з раніше зазначеними вершинами є вершини 4,5. З чого визначаємо? = Min { 2,4, 2,5, 3,4, 3,5} = 1 і після перетворення маємо 2,5 = 8, 2 ...
