Главное меню

Вход на сайт

Кто на сайте?

Сейчас 146 гостей и ни одного зарегистрированного пользователя на сайте

В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1
Image

Решение

Составим таблицу пошагово:

 
 1  2  3  4  5   6
  7
 8 
s
Х1
 ∞  ∞  ∞  ∞  ∞ 7,X27,X27,X4
  X2  ∞  ∞  ∞6,X54,X3   
  X3  ∞3,X43,X43,X4    
t X40,X4       
  X5  ∞2,X42,X4     
  X6  ∞1,X4      
  X7  ∞  ∞  ∞9,X59,X56,X26,X2 
  X8  ∞  ∞4,X64,X64,X64,X6  

На первом шаге вершине S присваиваем метку (0, S), а остальным ( ∞). Выбираем из всех меток наименьшую (y, X4) и делаем её постоянной. Из этой «постоянной» вершины пытаемся пометить достижимые из неё вершины и присваиваем метку:
метка = min(старая метка, метка постоянной вершины + длина ребра).
Метки недостижимых вершин сохраняются. У постоянных вершин метки не меняют точки. Процесс продолжаем, пока постоянной меткой не будет помечена вершина t. Метка вершины t равна длине кратчайшего пути. В нашем случае Lмм=7.
Маршрут восстанавливаем из второй части меток, которые содержат индекс вершины, из которых они помечены.
Тогда кратчайший маршрут: (Х1, Х2, Х3, Х4) или (Х4, Х3, Х2, Х1).

У Вас недостаточно прав для добавления комментариев.
Вам необходимо зарегистрироваться на сайте