ustify"> ij матриці D k-1 . Якщо виконується нерівність d ik + d kj ij , (i <> k, j <> k, i <> j), тоді виконуємо наступні дії:
В· створюємо матрицю D k шляхом заміни в матриці D k-1 елемента d ij на суму d ik + d kj ,
В· створюємо матрицю S k шляхом заміни в матриці S k-1 елемента s ij на k. Вважаємо k = k + 1 і повторюємо крок k.
Пояснимо дії, виконувані на k-му кроці алгоритму, представивши матрицю D k-1 так, як вона показана на малюнку 2.3. На цьому малюнку рядок k і стовпець k є провідними. Рядок i - будь-яка рядок з номером від 1 до k - 1, а рядок p - довільна рядок з номером від k + 1 до n. Аналогічно стовпець j являє будь стовпець з номером від 1 до k - 1, стовпець q - довільний стовпець з номером від k + 1 до n. Трикутний оператор виконується наступним чином. Якщо сума елементів провідних рядка і стовпчика (показаних у квадратах) менше елементів, що у перетині стовпчика і рядка (показаних у гуртках), відповідних розглядаються провідним елементам, то відстань (елемент в гуртку) замінюється на суму відстаней, представлених провідними елементами:
В
Рис 2.3. Ілюстрація алгоритму Флойда
Після реалізації n кроків алгоритму визначення по матрицях D n і S n найкоротшого шляху між вузлами i та j виконується за такими правилами.
1. Відстань між вузлами i та j одно елементу d ij в матриці D n .
2. Проміжні вузли шляху від вузла i до вузла j визначаємо по матриці S n . Нехай s ij = k, тоді маємо шлях i -> k -> j. Якщо далі s
