 |
 |
 |
 |
|
 |
 |
73
Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2.
Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m3 = 1 (рис. 3.7).
Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными
вершинами являются вершины 4,5. Из чего определяем ? = min{
с
~
2,4
,
с
~
2,5
,
с
~
3,4
,
с
~
3,5
}=1 и после пре-
образования имеем
с
~
2,4
= 8,
с
~
2,5
=
0,
с
~
3,4
= 3,
с
~
3,5
= 5.
Итерация 4. Помечаем вершину 4 m
4
=2 (см. рис. 3.8). Дальнейшая пометка невозможна, поэтому
переходим к этапу 2. Смежными с ранее помеченными вершинами являются вершины 5,6. Из чего
определяем
? = min{
с
~
2,5
,
с
~
3,5
,
с
~
4,5
,
с
~
4,6
}=3 и после преобразования имеем
с
~
2,5
=
5,
с
~
3,5
= 0,
с
~
4,5
= 0,
с
~
4,6
= 5.