+ dkj lt; dij, (i lt; gt; k, j lt; gt; k, i lt; gt; j), тоді виконуємо наступні дії:
· створюємо матрицю Dk шляхом заміни в матриці Dk - 1 елемента dij на суму dik + dkj,
· створюємо матрицю Sk шляхом заміни в матриці Sk - 1 елемента sij на k. Вважаємо k=k + 1 і повторюємо крок k.
Пояснимо дії, що виконуються на k-му кроці алгоритму, представивши матрицю Dk - 1 так, як вона показана на малюнку 4. 5. На цьому малюнку рядок k і стовпець k є провідними. Рядок i - будь-який рядок з номером від 1 до k - 1, а рядок p - довільна рядок з номером від k + 1 до n. Аналогічно стовпець j являє будь стовпець з номером від 1 до k - 1, стовпець q - довільний стовпець з номером від k + 1 до n. Трикутний оператор виконується наступним чином. Якщо сума елементів провідних рядка і стовпця (показаних в квадратах) менше елементів, що знаходяться в перетині стовпця і рядка (показаних у гуртках), відповідних розглянутим провідним елементам, то відстань (елемент в гуртку) замінюється на суму відстаней, представлених провідними елементами:
Схема 4.5 Ілюстрація алгоритму Флойда
Після реалізації n кроків алгоритму визначення за матрицями Dn і Sn найкоротшого шляху між вузлами i та j виконується за такими правилами.
Відстань між вузлами i та j одно елементу dij в матриці Dn.
Проміжні вузли шляху від вузла i до вузла j визначаємо по матриці Sn. Нехай sij=k, тоді маємо шлях i - gt; k - gt; j. Якщо далі sik=k і skj=j, тоді вважаємо, що весь шлях визначений, так як знайдені всі проміжні вузли. В іншому випадку повторюємо описану процедуру для шляхів від вузла i до вузла k і від вузла k до вузла j (рис. 4.6).
Рис 4.6 Трикутний оператор
4.5 Розрахунок математичної моделі
Складемо для поставленої задачі зображеної на малюнку 4.4. матрицю суміжності, отримаємо матрицю D0 (рис. 4.7.)
Рис 4.7 Первісна матриця
Застосуємо до неї алгоритм Флойда, отримаємо таку матрицю найкоротших шляхів і матрицю маршрутів (рис 4.8.):
Рис. 4.8 Результат роботи алгоритму
Таким чином, наприклад, найкоротша відстань з першої вершини в другу одно 4. З шостий в сьому одно 9, причому проходимо через 5-ю вершину, з п'ятої в першу відстань дорівнює 10, і проходимо через 7-ю вершину (рис. 4.9.)
Рис. 4.9 Результат роботи алгоритму показаний на графі
Шлях з 6 в 9 дорівнює 2 + 7=9.Путь з 1 в 2 дорівнює 4
Перенумеруем вузли по іншому (рис.4.10)
Рис.4.10. Друге завдання
Складемо для поставленої задачі зображеної на малюнку 4.4. матрицю суміжності, отримаємо матрицю D0 ріс.4.11.
Ріс.4.11 Первісна матриця до другій задачі
Застосуємо до неї алгоритм Флойда, отримаємо таку матрицю найкоротших шляхів і матрицю маршрутів (рис.4.12.):
Рис 4.12 Результат роботи алгоритму
Таким чином, наприклад, найкоротша відстань з першої вершини в третю дорівнює 7, шлях проходить через 2-ю вершину. З шостої до четверту одно 7, причому проходимо через 7-ю вершину (рис.4.13.).
рис.4.13. Результат роботи алгоритму показаний на графі
Перенумеруем вузли по іншому (ріс.4.14.).
Ріс.4.14 Третє завдання
Складемо для поставленої задачі зображеної на малюнку 13 матрицю суміжності, отримаємо матрицю D0 (ріс.4.15.).
Ріс.4.15 Первісна матриця до третьої завданню
Застосуємо до неї алгоритм Флойда, отримаємо таку матрицю найкоротших шляхів і матрицю маршрутів (ріс.4.16.):
Ріс.4.16 Результат роботи алгоритму
Таким чином, наприклад, найкоротша відстань з третьої вершини в шосту одно 10, шлях проходить через 5-ю вершину. Із сьомої в другу одно 7, причому проходимо через 1-ю вершину.
ВИСНОВКИ
З розвитком комп'ютерної техніки і комп'ютеризацією виробництва та інших галузей людської діяльності, безперервно зростає роль дискретної математики як теоретичної основи для побудови алгоритмів і написання комп'ютерних програм.
Теорія графів - дуже важливий розділ дискретної математики, особливістю якого є геометричний підхід до вивчення об'єктів. Діаграми графа подібно геометричним рисунків дозволяють отримати наочне уявлення до різног...
