року 2.
Шоста ітерація.
КРОК 2. Знаходімо Г (х9)={х1, х2, х6, х7, х8}. Саме вершина х6 тимчасова, отже перераховуємо ее значення: L (х6)=min [17,11 + 9]=17.
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові Позначки вершин: L (х3)=23, L (х5)=12, L (х6)=17.
Очевидно, что мінімальну Позначку, рівну 12 має вершина х5.
КРОК 4. За Наступний поточних мітку пріймаємо вершину х5, тобто p=х5, а ее мітка становится постійною, L (х5)=12 +.
КРОК 5. Оскількі НЕ всі вершини графа мают постійні Мітки, Переходимо до Кроку 2.
Сьома ітерація.
КРОК 2. Знаходімо Г (х5)={х4, х6}. Позначку вершини х6 тимчасова, отже, перераховуємо ее значення:
(х6)=min [17,12 + 10]=17.
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові Позначки: (х3)=23, L (х6)=17.
Очевидно, что мінімальну Позначку, рівну 17 має вершина х6.
КРОК 4. За Наступний поточних Позначку пріймаємо вершину х6, тобто p=х6, а ее Позначку становится постійною, L (х6)=17 +.
КРОК 5. Оскількі НЕ всі вершини графа мают постійні Позначки, Переходимо до Кроку 2.
восьми ітерація.
КРОК 2. Знаходімо Г (х6)={х3, х5, х7, х8, х9}. Позначку вершини х3 тимчасова, отже, перераховуємо ее значення: L (х3)=min [23,17 + 20]=23.
КРОК 3. На даного кроці ітерації маємо одну тимчасову Позначку вершини: L (х3)=23, яка становится постійною.
КРОК 4. Всі вершини мают постійні Мітки, того алгоритм закінчений. Для знаходження найкоротшого шляху между вершинами, например, х2 и початково х1 послідовно вікорістовуємо співвідношення:
(x 2) + c (x 2, x2)=L (x2)=5, (5.3)
де вершина x'2 - це вершина, безпосередно передуюча x2 в найкоротшому шляху від х1 до x2. Єдиною такою вершиною є вершина х7. Далі відношення (5.3) застосовуємо другий раз:
(x 7) + с (x 7, x7)=L (x7)=3 (5.4)
Єдиною такою вершиною є вершина х1. Тому найкоротшій шлях від х1 до x2 є ПЕРЕЛІК вершин: х1, х7, х2.
Вершина х1, є базою та надає всі найкоротші шляхи від х1, Які Надано на ріс.5.34.
Дев ята ітерація. Кінець алгоритму.
Малюнок 5.34 - Вершина х1 є базовою вершиною
. 10.4 Алгоритм Флойда
Алгоритм Флойда - Динамічний алгоритм для находження найкоротшіх відстаней между усіма вершинами зваження орієнтованого графа. Розроблення у тисячу дев'ятсот шістьдесят-два году Робертом Флойдом. Роберт Флойд (англ. Robert Floyd, 8 червня 1936 року, Нью-Йорк, США - 25 вересня 2001 року, Стенфорд, США) - американський вчений в області Теорії обчислювальних систем. Мав нагороди: у 1978 году - премія Тюрінга за его Безперечно Вплив на методологію создания ефективного и надійного програмного забезпечення и за его допомогу в становленні таких областей комп'ютерних наук як семантика мов програмування, автоматична веріфікація програм, автоматичний синтез програм, і аналіз алгоритмів" , у 1991 році - премія піонера обчіслювальної техніки (англ. Computer Pioneer Award) від IEEE [4].
Припустиме, что ми маємо поміченій орграф, Який містіть годину польоти по маршрутах, что зв'язують певні міста.
Припустиме, что необходимо побудуваті таблицю, де пріводівся бі мінімальній годину перельот з одного (довільного) міста в будь-який іншій. У цьом випадка ми стікаємося Із загальною задачею знаходження найкоротшіх Шляхів, тобто знаходження найкоротшіх Шляхів между всіма парами вершин орієнтованого графа.
Формулювання Завдання. Надано орієнтований граф G=(X, A), Кожній дузі (ребру) (u, w) цього графу відповідає невід ємна вага C u w. Загальна задача знаходження найкоротшіх Шляхів Полягає в знаходженні для кожної впорядкованої парі вершин (u, w) будь-которого шляху від вершини u у вершину w, довжина которого є мінімальною среди всех можливіть Шляхів від u до w.
Можна розв язувати Цю задачу, послідовно застосовуючі алгоритм Дейкстри для кожної вершини, что Оголошується як джерело. Альо для розв язання поставленої задачі можна скористати алгоритмом, запропонованім Флойдом.
Припустиме, что всі вершини орграфа послідовно пронумеровані від 1 до n. Алгоритм Флойда вікорістовує матрицю A (n, n), В якій знаходяться Довжина найкоротшіх Шляхів:=Cij, если i? J;=0, если i=j; j =? , Если відсутній шлях з вершини i у вершину j.
Над матрицею A віконується n ітерацій. После k-ої ітерації Aij містіть значенн...
