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

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