40. Проаналізувати роботу алгоритму Дейкстри.

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

Крок 1. Ініціалізація. Відстань до всіх вершин графа V =  . Відстань до а = 0. Жодна вершина графа ще не опрацьована.

Крок 2. Знаходимо таку вершину (із ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда.

Крок 3. Перший по порядку сусід 1-ї вершини — 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.

Кроки 4, 5. Аналогічну операцію проробляєм з двома іншими сусідами 1-ї вершини — 3-ю та 6-ю.

Крок 6. Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною і обговоренню не підлягає (те, що це дійсно так, вперше довів Дейкстра). Тому викреслимо її з графа, щоб відмітити цей факт. 

Крок 7. Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7.  І знову намагаємося зменшити відстань до всіх сусідів 2-ої вершини, намагаючись пройти в них через 2-у. Сусідами 2-ої вершини є 1, 3, 

Крок 8. Перший (по порядку) сусід вершини № 2 — 1-а вершина. Але вона вже оброблена (або викреслена — див. крок 6). Тому з 1-ою вершиною нічого не робимо.

Крок 9. Ще один сусід вершини 2 — вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини № 3 і дорівнює 9, тому поточну відстань до 3-ої вершини не міняємо. 

Крок 10. Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і викреслюємо її з графа. 

Кроки 11 — 15. По вже «відпрацьованій» схемі повторюємо кроки 2 — 6. Тепер «найближчою» виявляється вершина № 3. 

Наступні кроки. Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).

Завершення виконання алгоритму. Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ої вершини до 2-ої становить 7, до 3-ої — 9, до 4-ої — 20, до 5-ої — 20, до 6-ої — 11 умовних одиниць.

41.Розкрити алгоритм флойда.

А лгоритм Флойда-Воршелла — алгоритм динамічного програмування для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений в 1962 році Робертом Флойдом і Стівеном Воршеллом. Нехай вершини графа   пронумеровані від 1 до   і введено позначення   для довжини найкоротшого шляху

в ід   до  , який окрім самих вершин  проходить тільки через вершини  . Очевидно, що   — довжина (вага)

р ебра  , якщо воно існує (в іншому разі його довжина може бути позначена як  )

Існує два варіанти значення :

Н айкоротший шлях між   не проходить через вершину  , тоді 

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