додається x i *, то припущення, що l (x i *) дорівнює довжині найкоротшого шляху x i S 1 , виконується при кожній ітерації. Звідси по індукції випливає, що алгоритм дає оптимальну відповідь.
Якщо потрібно знайти найкоротші шляхи між s та всіма іншими вершинами повного зв'язного графа з n вершинами, то в процесі роботи алгоритму виконуються операцій складання та порівняння на кроці 2 і ще операцій порівняння на кроці 3. Крім того, при здійсненні кроків 2 і 3 необхідно визначити, які вершини тимчасові, а для цього потрібно ще операцій порівняння. Ці величини є верхніми границями для числа операцій, необхідних при відшуканні найкоротшого шляху між заданими вершинами s і t. Вони дійсно досягаються, якщо виявиться, що вершина t буде останньою вершиною, що отримала постійну позначку.
Як тільки довжини найкоротших шляхів від s будуть знайдені (вони будуть заключними значеннями позначок вершин), самі шляху можна отримати за допомогою рекурсивної процедури з використанням співвідношення (*). Так як вершина x i 'безпосередньо передує вершині x i в найкоротшому шляху від s до x i , то для будь-якої вершини x i відповідну вершину x i 'можна знайти як одну з залишилися вершин, для якої
''. (*)
Якщо найкоротший шлях від s до будь-якої вершини x i є єдиним, то дуги (x i ', x i ) цього найкоротшого шляху утворюють орієнтоване дерево з коренем s. Якщо існує кілька В«найкоротшихВ» шляхів від s до якої-небудь іншої вершині, то при деякій фіксованій вершині x i 'співвідношення (*) буде виконуватися для більш ніж однієї вершини x i . У цьому випадку вибір може бути або довільним (якщо потрібен якийсь один найкоротший шлях між s і x i ), або таким, що розглядаються всі дуги (x i ', x i ), що входять до будь-якої з найкоротших шляхів і при цьому сукупність всіх таких дуг утворює не орієнтоване дерево, а загальний граф, званий базою щодо s або коротко - s- базою .
2.2 Завдання з методичним описом
Знайти найкоротші шляхи від вершини 1 до всіх інших вершин графа
неорієнтованих ребро будемо розглядати як пару протилежно орієнтованих дуг рівного ваги. Скористаємося алгоритмом Дейкстри. Постійні позначки будемо постачати знаком +, решта позначки розглядаються як тимчасові.
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8
x 9
x 1
10
3
6
12
x 2
10
18
2
13
x 3
18
25
20
7
x 4
25
5
16
4
x 5
5
10
x 6
20
10
14
15
9
x 7
2
4
14
24
x 8
6
23
15
5
x 9
12
13
9
24
5
Алгоритм працює так:
Крок 1 . .
Перша ітерація
Крок 2 . - Всі позначки тимчасові.
;;;
Крок 3 . відповідає x 7 .
Крок 4 . x 7 отримує постійну позначку l (x 7 ) = 3 + , p = x 7 .
Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.
Друга ітерація
Крок 2 . - Всі позначки тимчасові.
;;;
Крок 3 . відповідає x 2 .
Крок 4 . x 2 отримує постійну позначку l (x 2 ) = 5 + , p = x 2 .
Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.
Третя ітерація
Крок 2 . - Тільки вершини x 3 і x 9 мають тимчасові позначки.
;
Крок 3 . відповідає x 8 .
Крок 4 . x 8 отримує постійну позначку l (x 8 ) = 6 + , p = x 8 .
Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.
Четверта ітерація
Крок 2 . - Ті...
