КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Решение
Рис. 11
Превращаем граф в нагруженный, подставляя веса ребер слева направо (по оси Ox) и снизу вверх (по оси Oy) (рис. 11); б) действуем по алгоритму: вершине А приписываем индекс 0, остальным вершинам + . Вершины, смежные с А, получают новые индексы: вершина (0; 1): 0 + 9 = 9, вершина (1; 0): 0 + 7 = 7. Вершина (1; 1) может получить индекс 7 + 4 = 11 или 9 + 6 = 15. выбираем наименьший из возможных индексов – 11 (рис 12).
Рис 12
Действуя аналогичным образом, присваиваем новые индексы всем вершинам. При этом вершина В получает индекс 27 (рис. 13).
Рис. 13
Индекс 27 = 26 + 1, следовательно, из вершины В нужно идти вниз, в вершину (4; 3) с индексом 26. 26 = 25 + 1, из вершины (4; 3) переходим в вершину (3; 3) с индексом 25. Этот индекс может быть получен двумя способами: 25 = 23 + 2 = 18 + 7, т.е. получаем два пути. 18 = 17 + 1, 23 = 17 + 6; оба пути сходятся в вершине (2; 2). 17 = 16 + 1; 16 = 11 + 5; 11 = 7 + 4; 7 = 0 + 7. мы вернулись в вершину А. Таким образом, построены два пути с наименьшей суммой весов, равной 27 (рис. 14).
Рис. 14
Вот эти пути: и
Дата добавления: 2014-11-20; Просмотров: 727; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |