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

Четвертая итерация

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

Вторая итерация

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

Ш А Г 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(р) = Г(х₁) = { х₂, х₇, х₈, х₉ }. Все вершины, входящие в прямое отображение имеют временные пометки, поэтому пересчитаем их значение:

L(x₂)=min[L(x₂),L(x₁) + c(x₁,x₂)]=min[∞,0+10]=10

L(x₇)=min[∞,0+3]=3

L(x₈)=min[∞,0+6]=6

L(x₉)=min[∞,0+12]=12

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₂) = 10, L(х₃) = ∞,

L(х₇) = 3, L(х₄) = ∞,

L(х₈) = 6, L(х₅) = ∞,

L(х₉) = 12, L(х₆) = ∞.

Очевидно, что минимальную метку, равную 3, имеет вершина х₇.

Ш А Г 4. За следующую текущую метку принимаем верши- ну х₇, т. е. p = х₇, а ее метка становится постоянной, L(х₇) = 3⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

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

Рис. 9.3. Пометки в конце первой итерации

Ш А Г 2. Находим Г(х₇) = { х₂, х₄, х₆, х₉}. Метки всех вершин временные, следовательно пересчитываем их значения:

L(х₂)= min [10, 3 + 2 ] = 5,

L(х₄)= min [ ∞, 3 + 4 ] = 7,

L(х₆)= min [ ∞, 3 + 14 ] = 17,

L(х₉)= min [ 12, 3 + 24 ] = 12.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₂) = 5, L(х₃) = ∞,

L(х₄) = 7, L(х₅) = ∞,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

Очевидно, что минимальную метку, равную 5, имеет вершина х₂.

Ш А Г 4. За следующую текущую метку принимаем вершину х₂, т. е. p = х₂, а ее метка становится постоянной, L(х₂) = 5⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

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

Рис. 9.4. Пометки в конце второй итерации

Ш А Г 2. Находим Г(х₂) = {х₁, х₃, х₇, х₉}. Метки вершин х₃ и х₉ временные, следовательно пересчитываем их значения:

L(х₃) = min [ ∞, 5 + 18 ] = 23,

L(х₉) = min [ 12, 5+13 ] = 12.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₃) = 23, L(х₄) = 7, L(х₅) = ∞,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

Очевидно, что минимальную метку, равную 6, имеет вершина х₈.

Ш А Г 4. За следующую текущую метку принимаем вершину х₈, т. е. p = х₈, а ее метка становится постоянной, L(х₈) = 6⁺.

Ш А Г 5. Не все вершины графа имеют постоянные метки, поэтому переходим к шагу 2.

Ш А Г 2. Находим Г(х₈) = { х₁, х₅, х₆, х₉ }. Метки вершин х₅, х₆ и х₉ временные, следовательно, пересчитываем их значения:

L(х₅) = min [ ∞, 6 + 23 ] = 29,

L(х₆) = min [ 17, 6 + 15 ] = 17,

L(х₉) = min [ 12, 6 + 5 ] = 11.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₃) = 23, L(х₄) = 7,

L(х₅) = 29, L(х₆) = 17, L(х₉) = 11.

Очевидно, что минимальную метку, равную 7 имеет вершина х₄.

Ш А Г 4. За следующую текущую метку принимаем вершину х₄, т. е. p = х₄, а ее метка становится постоянной, L(х₄) = 7⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Ш А Г 2. Находим Г(х₄) = { х₃, х₅, х₆, х₇ }. Метки вершин х₃, х₅ и х₆ временные, следовательно, пересчитываем их значения:

L(х₃) = min [ 23, 7 + 25 ] = 23,

L(х₅)= min [ 29, 7 + 5 ] = 12,

L(х₆)= min [17, 7 + 16] = 17.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₃) = 23, L(х₅) = 29,

L(х₆) = 17, L(х₉) = 11.

Очевидно, что минимальную метку, равную 11 имеет вершина х₉.

Ш А Г 4. За следующую текущую метку принимаем вершину х₉, т. е. p = х₉, а ее метка становится постоянной, L(х₉) = 11⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.