tify"> Алгоритм Флойда вимагає виконання наступних дій.
Крок 0 . Визначаємо початкову матрицю відстані D 0 і матрицю послідовності вузлів S 0. Діагональні елементи обох матриць позначаються знаком - raquo ;, що показує, що ці елементи в обчисленнях не беруть участь. Вважаємо k=1:
Рис. 17. Початкова ситуація
Основний крок k . Задаємо рядок k і стовпець k як провідну рядок і провідний стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів d ij матриці D k - 1. Якщо виконується нерівність d ik + d kj lt; d ij, (i lt; gt; k, j lt; gt; k, i lt; gt; 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 так, як вона показана на малюнку 3. На цьому малюнку рядок k і стовпець k є провідними. Рядок i - будь-який рядок з номером від 1 до k - 1, а рядок p - довільна рядок з номером від k + 1 до n. Аналогічно стовпець j являє будь стовпець з номером від 1 до k - 1, стовпець q - довільний стовпець з номером від k + 1 до n. Трикутний оператор виконується наступним чином. Якщо сума елементів провідних рядка і стовпця (показаних в квадратах) менше елементів, що знаходяться в перетині стовпця і рядка (показаних у гуртках), відповідних розглянутим провідним елементам, то відстань (елемент в гуртку) замінюється на суму відстаней, представлених провідними елементами:
Рис. 18. Ілюстрація алгоритму Флойда
Після реалізації n кроків алгоритму визначення за матрицями D n і S n найкоротшого шляху між вузлами i та j виконується за такими правилами.
Відстань між вузлами i та j одно елементу d ij в матриці D n.
Проміжні вузли шляху від вузла i до вузла j визначаємо по матриці S n. Нехай s ij=k, тоді маємо шлях i - gt; k - gt; j. Якщо далі s ik=k і s kj=j, тоді вважаємо, що весь шлях визначений, так як знайдені всі проміжні вузли. В іншому випадку повторюємо описану процедуру для шляхів від вузла i до вузла k і від вузла k до вузла j.
Приклад. Знайдемо для мережі, показаної на малюнку 4, найкоротші шляхи між будь-якими двома вузлами. Відстань між вузлами цієї мережі проставлені на малюнку біля відповідних ребер. Ребро (3, 5) орієнтовано, тому не допускається рух від вузла 5 до вузла 3. Всі інші ребра допускають рух в обидві сторони:
Рис. 19. Приклад мережі
Крок 0 . Початкові матриці D 0 і S 0 будуються безпосередньо за заданою схемою мережі. Матриця D 0 симетрична, за винятком пари елементів d 35 і d 53, де d 53 одно нескінченності, оскільки неможливий перехід від вузла 5 до вузла 3:
Рис.20. Початковий стан
Крок 1 . У матриці D 0 виділені провідні рядок і стовпець (k=1). Подвійною рамкою представлені елементи d 23 і d 32, єдині серед елементів матриці D 0, значення яких можна поліпшити за допомогою трикутного оператора. Таким чином, щоб на основі матриць D 0 і S 0 отримати матриці D 1 і S 1, виконуємо наступні дії.
Замінюємо d 23 на d 21 + d 13=3 + 10=13 і встановлюємо s 23=1.
Замінюємо d 32 на d 31 + d 12=10 + 3=13 і встановлюємо s 32=1.
Матриці D 1 і S 1 мають такий вигляд:
Рис.21. Матриці D 1 і S 1
Крок 2 . Вважаємо k=2; в матриці D 1 виділені провідні рядок і стовпець. Трикутний оператор застосовується до елементів матриці D 1 і S 1, виділеним подвійною рамкою. В результаті отримуємо матриці D 2 і S 2:
Рис.22. Матриці D 2 і S 2
Крок 3 . Вважаємо k=3; в матриці D 2 виділені провідні рядок і стовпець. Трикутний оператор застосовується до елементів матриці D 2 і S 2, виділеним подвійною рамкою. В результаті отримуємо матриці D 3 і S 3:
Рис.23. Матриці D 3 і S 3
Крок 4 . Вважаємо k=4, провідні рядок і стовпець у матриці D 3 виділені. Отримуємо нові матриці D 4 і S 4:
Рис.24. Матриці D 4 і S 4
Крок 5 . Вважаємо k=5, провідні рядок і стовпець у матриці D 4 виділені. Ніяких дій на цьому кроці не виконуються; обчислення закінчені.
Кінцеві матриці D 4 і S 4 містять всю інформацію, необхідну для визначення найкоротших шляхів між будь-якими дво...
