уку в графі найкоротшого шляху між усіма парами вершин.
Розглянемо приклад даної задачі зі сфери діяльності людини. Припустимо, що авіакомпанія, повинна для численних пасажирів щодня розробляти маршрути польотів між різними містами. Ця авіакомпанія в цілях економії своїх витрат прагне надавати пасажирам найбільш короткі маршрути. Тому їй хотілося б надавати пасажирам найбільш короткі маршрути. Очевидно, їй хотілося б заздалегідь знати найкоротші маршрути між кожною парою міст США, якщо, наприклад, мова йде про польоти в межах США.
Звичайно, ця задача могла б бути вирішена багаторазовим використанням алгоритму знаходження найкоротшого шляху між двома вершинами, проте реалізація відповідної процедури зажадала б порівняно великих обчислювальних витрат. Існують алгоритми більш ефективні, ніж процедура багаторазового повторення.
У цій роботі ми розглянемо алгоритм Флойда для знаходження найкоротших шляхів між усіма парами вершин графа. [6]
2.4 Алгоритм Флойда
Алгоритм Флойда - це алгоритм пошуку найкоротших шляхів між усіма вершинами графа.
Нехай дано зважений орграф з n вершинами і матрицею ваг W. Кожен елемент матриці ваг w дорівнює вазі дуги (Якщо такий дуги немає, то w), а w=0.
Припустимо, що граф не містить контурів негативною довжини. Пронумеруємо вершини графа від 1 до n. Позначимо W матрицю з елементами w, кожен з яких дорівнює довжині найкоротшого шляху з вершини i в вершину j, який може містити як проміжні вершин тільки перші k вершин графа. Якщо такого шляху не існує, то w =. W=W. По матриці W обчислюється матриця W, що містить найкоротші шляхи між усіма вершинами графа. Елементи матриці W на k-й ітерації обчислюються наступним чином:
=min, (2)
де w-довжина найкоротшого шляху з вершини i в вершину k, в якій в якості проміжних використовуються перші k - 1 вершини графа.
Для того, щоб по закінченні роботи алгоритму можна було швидко побудувати найкоротший шлях, на кожній ітерації разом з матрицею Wстроітся матриця P, кожен елемент якої p дорівнює номеру вершини, що передує вершині j в поточному ij шляху.
На поточному ітерації
p, і (3)=(4)
Номери вершин, що включаються в найкоротший шлях, визначаються таким чином: і т.д.
Основні кроки алгоритму:
. Пронумерувати вершини графа цілими числами k=0. Визначити матрицю W. Визначити матрицю P, p=i,, i, j=1. n і p=0,=1. n.
. Якщо k=n, робота алгоритму закінчена (W-ця матриця ваг найкоротших шляхів між усіма парами вершин графа, що визначаються за допомогою матриці P). Якщо kn, то k=k +1, перехід до кроку 3.
. Обчислити для всіх i, j=1 ... n елементи w=min. Якщо < , То p=p. Інакше p.
. Якщо для деякого 1 елемент с, то в графі є контур негативною довжини і робота алгоритму завершується. Інакше перейти до кроку 2. [1]
3. Розробка програми
Для зручності рішення поставленої задачі будемо використовувати модульне програмування. Для цього розіб'ємо рішення задачі на кілька етапів: введення вихідних даних, побудова графіків функції, визначення координат точок перетину і уточнення їх значень.
3.1 Характеристика програми і системні вимоги <...
