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


Пятая итерация

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


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

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

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