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