что показує, что ці елєменти в обчисления не беруть доля. Думаємо:
В
Рис. 3.2. Початкова Ситуація
Основний крок k . Задаємо рядок и стовпець як ведучий рядок и ведучий стовпець . Розглядаємо можлівість ! застосування трикутна оператора до всіх ЕЛЕМЕНТІВ матріці. Если віконується нерівність, тоді виконуємо наступні Дії:
В· Створюємо матрицю Шляхом заміні в матріці елемента на суму,
В· Створюємо матрицю Шляхом заміні в матріці елемента на. Думаємо и повторюємо крок.
Пояснімо Дії, віконувані на-му кроці алгоритмом, запропонувавши матрицю так, як вона показана на рис 3.3. На цьом малюнку рядок и стовпець є провідними. Рядок - будь-який рядок з номером від 1 до, а рядок - довільній рядок з номером від до. Аналогічно стовпець представляет будь-як стовпець з номером від 1 до, стовпець - довільній стовпець з номером від до. Трикутна оператор віконується в такий способ. Если сума ЕЛЕМЕНТІВ ведучих рядка и стовпця (свідчення у квадратах) менше ЕЛЕМЕНТІВ, что знаходяться в перетінанні стовпця и рядка (свідчення у гуртках), что відповідають Розглянуто ведучим Елемент, то відстань (елемент у кружку) заміняється на суму відстаней, представлених провідними елементами:
В
Рис. 3.3. Ілюстрація алгоритмом Флойда
После реалізації кроків алгоритму визначення по матриці и найкоротшому шляху между Вузли и віконується за Наступний правилами.
1. Відстань между Вузли и дорівнює елементові в матріці.
2. Проміжні Вузли шляху від Вузли до Вузли візначаємо по матріці. Нехай, тоді маємо шлях. Если далі І, тоді Вважаємо, что весь шлях визначеня, ТОМУ ЩО знайдені ВСІ проміжні Вузли. У противному випадка повторюємо описом процедуру для Шляхів від Вузли до Вузли и от Вузли до Вузли.
При аналізі транспортних мереж часто вінікає завдання визначення максимального потоку, что может Пропустити дана мережа, а такоже завдання розподілу цього потоку по дугах мережі.
З математичної точки зору завдання для найбільш Потік формулюється в такий способ: при заданій конфігурації мережі и відомої пропускної здатності найти ненегатівні значення, а что задовольняють умів и, что максімізують функцію, тоб
В
Алгоритм для знаходження максимального потоку БУВ запропонованій Фордом и Фалкерсоном и Полягає в поступовому збільшенні потоку, что пропускається по мережі, Доті, поки ВІН не стану найбільшім. Алгоритм Заснований на теоремі Форда-Фалкерсона: у будь-якій транспортній мережі Максимальний Потік Із джерела в СТІК, дорівнює мінімальній пропускній здатності розрізу, что відокремлює від.
Крок 0 . Прізначаємо вузлові 15 постійну мітку [0, -].
Крок 1 . З Вузли 15 можна досягті вузлів 21 12 Лютий. Обчіслюємо Мітки для ціх вузлів, у результаті одержуємо Наступний таблицю міток:
Вузол
Мітка
Статус Мітки
15
В
Постійна
21
[512,15]
Тимчасова
2
[237,15]
Тимчасова
Серед вузлів 21, 2, 12, вузол 12 має найменшого Значення відстані (U12 = 172). Тому статус Мітки цього Вузли змінюється на В«ПостійнаВ».
Крок 2 . З Вузли 12 можна потрапіті у Вузли 2, 23, 22. Одержуємо Наступний список вузлів. p> Тимчасовий статус Мітки [237,15] Вузли 2 заміняється на Постійний (U2 = 237).
Крок 3 . З Вузли 2 можна досягті вузлів 21, 22, 31. После обчислення міток одержимо Наступний їх список:
Вузол
Мітка
Статус Мітки
15
В
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Тимчасова
21
[370 +512,2] = [882,2]
Тимчасова
22
[1009,12]
Тимчасова
22
