напрямків дуг рівної ваги.
Матриця вагів Надал на рис. 5.31 (б). Потрібно найти всі найкоротші шляхи від вершини х1 до всієї решті вершин.
КРОК 1. Прівласнімо L (х1)=0, L (хi) =? для всіх хi, окрім х1. Покладемо р=х1.
Перша ітерація.
КРОК 2. Знайдемо Пряме відображення для поточної даної вершини:
Г (р)=Г (х1)={х2, х7, х8, х9}. Всі вершини, что входять в прямому відображення мают Тимчасові Позначки, того перерахуємо їх значення:
(x2)=min[L(x2),L(x1)+c(x1,x2)]=min[?,0+10]=10;(x7)=min[?,0+3]=3;(x8)=min[?,0+6]=6;(x9)=min[?,0+12]=12.
Малюнок 5.31 - Приклад поиска найкоротшого шляху:
а) граф; б) матриця вагів дуг
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові Позначки вершин:
(х2)=10, L (х3)=?, (х7)=3, L (х4)=?, (х8)=6, L (х5)=?, (х9) =12, L (х6)=?.
Очевидно, что мінімальну Позначку, яка дорівнює 3, має вершина х7.
КРОК 4. За Наступний поточних Позначку пріймаємо вершину х7, тобто p=х7, а ее Позначку становится постійною, L (х7)=3 +.
КРОК 5. Оскількі НЕ всі вершини графу мают постійні Позначки, Переходимо до Кроку 2.
Друга ітерація.
Граф з поточних значень позначок вершин Надано на ріс.5.32.
Малюнок 5.32 - Позначки в кінці Першої ітерації
КРОК 2. Знаходімо Г (х7)={х2, х4, х6, х9}. Позначки всех вершин Тимчасові, отже перераховуємо їх значення:
(х2)=min[10,3+2]=5,(х4)=min[?,3+4]=7,(х6)=min[?,3+14]=17,(х9)=min[12,3+24]=12.
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові Позначки вершин:
(х2)=5, L (х3) =? , (х4)=7, L (х5) =? , (х6)=17, L (х8)=6, L (х9)=12.
Очевидно, что мінімальну Позначку, рівну 5, має вершина х2.
КРОК 4. За Наступний поточних Позначку пріймаємо вершину х2, тобто p=х2, а ее Позначку становится постійною, L (х2)=5 +.
КРОК 5. Оскількі НЕ всі вершини графа мают постійні Позначки, Переходимо до Кроку 2.
Третя ітерація.
Граф з поточних значень позначок вершин Надано на рис. 5.33.
Малюнок 5.33 - Позначки в кінці Другої ітерації
КРОК 2. Знаходімо Г (х2)={х1, х3, х7, х9}. Поміткі вершин х3 и х9 Тимчасові, отже перераховуємо їх значення:
(х3)=min [?, 5 + 18]=23, (х9)=min [12,5 + 13]=12.
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові поміткі вершин:
L (х3)=23, L (х4)=7, L (х5) =? , (х6)=17, L (х8)=6, L (х9)=12.
Очевидно, что мінімальну мітку, рівну 6, має вершина х8.
КРОК 4. За Наступний поточних помітку пріймаємо вершину х8, тобто p=х8, а ее мітка становится постійною, L (х8)=6 +.
КРОК 5. Не всі вершини графа мают постійні поміткі, того Переходимо до Кроку 2.
Четверта ітерація.
КРОК 2. Знаходімо Г (х8)={х1, х5, х6, х9}. Поміткі вершин х5, х6 и х9 Тимчасові, отже, перераховуємо їх значення:
(х5)=min [?, 6 + 23]=29, (х6)=min [17,6 + 15]=17, (х9)=min [12,6 + 5] =11.
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові Позначки вершин:
(х3)=23, L (х4)=7, (х5)=29, L (х6)=17, L (х9)=11.
Очевидно, что мінімальну Позначку, рівну 7 має верші на х4.
КРОК 4. За Наступний поточних мітку пріймаємо вершину х4, тобто p=х4, а ее мітка становится постійною, L (х4)=7 +.
КРОК 5. Оскількі НЕ всі вершини графа мают постійні Позначки, Переходимо до Кроку 2.
П'ята ітерація.
КРОК 2. Знаходімо Г (х4)={х3, х5, х6, х7}. Позначки вершин х3, х5 и х6 Тимчасові, отже, перераховуємо їх значення:
L (х3)=min [23,7 + 25]=23, (х5)=min [29,7 + 5]=12, (х6)=min [17,7 +1 6]=17.
КРОК 3. На даного кроці ітерації маємо следующие Тимчасові Позначки вершин:
(х3)=23, L (х5)=29, (х6)=17, L (х9)=11.
Очевидно, что мінімальну Позначку, рівну 11 має вершина х9.
КРОК 4. За Наступний поточних Позначку пріймаємо вершину х9, тобто p=х9, а ее мітка становится постійною, L (х9)=11 +.
КРОК 5. Оскількі НЕ всі вершини графа мают постійні Позначки, Переходимо до К...
