Конспект лекций по предмету "Теория графов"

Узнать цену работы по вашей теме


Восьмая итерация

Ш А Г 2. Находим Г(х6) = { х3, х5, х7, х8, х9 }. Метка вершины х3 временная, следовательно, пересчитываем ее значение:
L(х3) = min [ 23, 17 + 20 ] = 23.
Ш А Г 3. На данном шаге итерации имеем одну временную метку вершины: L(х3) = 23, которая становится постоянной.
Ш А Г 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.
Для нахождения кратчайшего пути между вершинами, например, х2 и начальной х1 последовательно используем соотношение (**): L(x'2)+c(x'2,x2)=L(x2)=5, где вершина x'2 – это вершина, непосредственно предшествующая х2 в кратчайшем пути от х1 к х2 .
Единственной такой вершиной является вершина х7 . Далее соотношение (**) применяем второй раз:
L(x7')+ с(x7’, x7) = L(x7) = 3
Единственной такой вершиной является вершина х1 . Поэтому кратчайший путь от х1 к х2 есть (х1, х7, х2). Вершина х1 , называемая базой и дающая все кратчайшие пути от х1 представляет дерево.

Рис. 9.5.


Не сдавайте скачаную работу преподавателю!
Данный конспект лекций Вы можете использовать для создания шпаргалок и подготовки к экзаменам.

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации