Інформатика – Поглиблений рівень

Прочитайте! 

Інкасатор щоденно відвідує магазини atb і може потрапляти від будь-якого магазину до всіх інших найкоротшим шляхом. У такому випадку найкоротшу відстань можна знайти за допомогою алгоритму Флойда — Уоршелла.

Ви знаєте, що для визначення найкоротшого шляху графу можна скористатися алгоритмом Дейкстри і в циклі обійти всі вершини. Розглянемо алгоритм Флойда — Уоршелла, який відрізняється від нього тим, що дозволяє знайти найкоротшу відстань не тільки від однієї вершини графу до всіх інших, а й від кожної вершини до всіх інших. Згадаємо, що графи, які можуть одночасно використовуватися і дуги, і ребра, називають змішаними. Розглянемо сутність алгоритму Флойда — Уоршелла на прикладі змішаного зваженого графу (рис. 8.22), сформулюємо алгоритм у загальному вигляді.

Розглянемо загальний зміст алгоритму Флойда — Уоршелла для графу з кількістю вершин n.

Програму реалізації алгоритму зображено на рис. 8.23.

Запустимо програму і перевіримо її роботу на прикладі такої матриці суміжності:

Виконайте програму на рис. 8.23 для графу, зображеного на рис. 8.26.