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

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


Третья итерация

Граф с текущими значениями меток вершин показан на рис. 9.4.

Рис. 9.4. Пометки в конце второй итерации
Ш А Г 2. Находим Г(х2) = {х1, х3, х7, х9}. Метки вершин х3 и х9 временные, следовательно пересчитываем их значения:
L(х3) = min [ ∞ , 5 + 18 ] = 23,
L(х9) = min [ 12, 5+13 ] = 12.
Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:
L(х3) = 23, L(х4) = 7, L(х5) = ∞ ,
L(х6) = 17, L(х8) = 6, L(х9) = 12.
Очевидно, что минимальную метку, равную 6, имеет вершина х8 .
Ш А Г 4. За следующую текущую метку принимаем вершину х8 , т. е. p = х8 , а ее метка становится постоянной, L(х8) = 6+ .
Ш А Г 5. Не все вершины графа имеют постоянные метки, поэтому переходим к шагу 2.


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

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

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

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

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