d (x)=min {d (x); d (y) + a (y, x)}
Мінімальну довжину має шлях від вершини 1 до вершини 4 d (4)=7. Включаємо вершину №4 в поточне орієнтоване дерево, а так само дугу, провідну в цю вершину. Згідно з виразом це дуга (1,4)
Ми отримали орієнтоване дерево найкоротших шляхів починаються у вершині №1 для вихідного графа.
(1)=1 Довжина маршруту L=0; (2)=1-4-2 Довжина маршруту L=16; (3)=1-4-2-5-6-3 Длінамаршрута L=63; ( 4)=1-4 Довжина маршруту L=7; (5)=1-4-2-5 Довжина маршруту L=25; (6)=1-4-2-5-6Дліна маршруту L=48.
Завдання 2
Дан граф суміжності для знаходження мінімального шляху від вершини 1 до всіх інших
Рис. 4.2. Граф до задачі 2
Уявімо граф, у вигляді матриця довжин дуг
Таблиця 2 Подання графа
X1X2X3X4X5X6x10532 ?? x2? 01 ??? x3 ?? 0 ?? 1x4 ??? 0? 3x5? 2 ?? 0? x6 ???? 10
Стартова вершина, від якої будується дерево найкоротших шляхів - вершина 1.
Задаємо стартові умови: d (1)=0, d (x) =?
Офарблюємо вершину 1, y=1.
Знаходимо найближчу вершину до пофарбованої нами, використовуючи формулу:
d (x)=min {d (x); d (y) + a (y, x)} (2)=min {8} (3)=min {9} (4)=min {2}
d (5)=min {6} (6)=min {5}
Мінімальну довжину має шлях від вершини 1 до вершини 4 d (4)=2. Включаємо вершину №4 в поточне орієнтоване дерево, а так само дугу, провідну в цю вершину. Згідно з виразом це дуга (1,4)
Ми отримали орієнтоване дерево найкоротших шляхів починаються у вершині №1 для вихідного графа.
d (1)=1Дліна маршрутаL=0; (2)=1-4-6-5-2 Довжина маршруту L=8; (3)=1-4-6-5-2-3 Довжина маршруту L =9; (4)=1-4 Довжина маршруту L=2; (5)=1-4-6-5 Довжина маршруту L=6; (6)=1-4-6 Довжина маршруту L=5.
4.3 Побудова математичної моделі алгоритмом Флойда
Мета алгоритму Флойда - визначення найкоротшого шляху між вершинами зваженого графа. Цей алгоритм більш загальний порівняно з алгоритмом Дейкстри, оскільки він знаходить найкоротші шляхи між будь-якими двома вузлами мережі. У цьому алгоритмі мережа представлена ??у вигляді квадратної матриці з n рядками і n стовпцями. Елемент (i, j) дорівнює відстані dij від вузла i до вузла j, яке має кінцеве значення, якщо існує дуга (i, j), і дорівнює нескінченності в іншому випадку.
Постановка завдання: нехай дан непорожній зважений граф G=(V, E) з довільними вагами ребер (дуг). Потрібно знайти довжини найкоротших шляхів між усіма парами вершин графа
Стосовно до прикладної задачі метою розробки програми є - визначення найбільш ефективного маршруту пересилки повідомлень між будь-якими двома районами. Причому алгоритм може вирішувати подібні завдання для різних критеріїв, наприклад, критерієм може бути - пошук найбільш дешевого шляху (кожній дузі ставиться у відповідність грошовий еквівалент, який необхідно затратити при використанні цієї дуги); або пошук найбільш швидкого шляху (в цьому випадку кожній дузі присвоюється час, який буде витрачено при її використанні); можна таким же чином знайти найнадійніший шлях (кожній дузі ставиться у відповідність коефіцієнт ризику передачі повідомлення по цій дузі/шляху).
Подібних завдань може виникнути дуже багато, а мета цих завдань однакова - знаходження найкоротшого шляху з одного стану в інший (щодо графа - знаходження мінімальної відстані між 2-ма вершинами).
4.4 Опис математичного методу алгоритму Флойда
Основна ідея методу Флойда полягає в наступному: нехай є три вузли i, j і k і задані відстані між ними (рис. 4.3.).
Якщо виконується нерівність dij + djk lt; dik, то доцільно замінити шлях i - gt; k шляхом i - gt; j - gt; k.
Така заміна (умовно звана трикутним оператором) виконується систематично в процесі виконання алгоритму Флойда.
Рис. 4.3 Трикутний оператор
Алгоритм Флойда вимагає виконання наступних дій (рис. 4.4.).
Крок 0. Визначаємо початкову матрицю відстані D0 і матрицю послідовності вузлів S0. Діагональні елементи обох матриць позначаються знаком - raquo ;, що показує, що ці елементи в обчисленнях не беруть участь. Вважаємо k:=1.
Рис.4.4 Первісна ситуація
Основний крок k. Задаємо рядок k і стовпець k як провідну рядок і провідний стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів dij матриці Dk - 1. Якщо виконується нерівність dik...
