Материал: 4442

31

d i min d i , d d a d, i min , 6 .

Поскольку величина d(b) = 11 является минимальной из величин d(a), d(b), d(c), d(e), d(f), d(g), d(h) и d(i), то вершина b окрашивается. Также окрашивается и дуга (a, b), которая и определяет величину d(b). Текущее дерево кратчайших путей состоит из дуг (a, d) и (a, b) (рисунок 4 б).

Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2. (у = b).

d c min d c , d b a b, c min , 11 20 31,

d e min d e , d b a b, e min 13, 11 12 13,

d f min d f , d b a b, f min , 11 18 29,

d g min d g , d b a b, g min 18, 11 18,

d h min d h , d b a b, h min 14, 11 14,

d i min d i , d b a b, i min , 11 .

Поскольку величина d(e) = 13 является минимальной из величин d(a), d(c), d(e), d(f), d(g), d(h) и d(i), то вершина e окрашивается. Также окрашивается и дуга (d, e), которая и определяет величину d(e). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b) и (d, e) (рисунок 4 в).

Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2. (у = e).

d c min d c , d e a e, c min 31, 13 31,

32

d f min d f , d e a e, f min 29, 13 3 16, d g min d g , d e a e, g min 18, 13 18,

d h min d h , d e a e, h min 14, 13 19 14,

d i min d i , d e a e, i min , 13 7 20.

Поскольку величина d(h) = 14 является минимальной из величин d(a), d(c), d(f), d(g), d(h) и d(i), то вершина h окрашивается. Также окрашивается

и дуга (d, h), которая и определяет величину d(h). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e) и (d, h) (рисунок 4 г).

Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2. (у = h).

d c min d c , d h a h, c min 31, 14 31, d f min d f , d h a h, f min 16, 14 16,

d g min d g , d h a h, g min 18, 14 11 18,

d i min d i , d h a h, i min 20, 14 29 20.

Поскольку величина d(f) = 16 является минимальной из величин d(a), d(c), d(f), d(g), и d(i), то вершина f окрашивается. Также окрашивается и дуга (e, f), которая и определяет величину d(f). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e), (d, h) и (e, f) (рисунок 4 д).

Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2. (у = f).

d c min d c , d f a f , c min 31, 16 11 27,

33

d g min d g , d f a f , g min 18, 16 18,

d i min d i , d f a f , i min 20, 16 24 20.

Поскольку величина d(g) = 18 является минимальной из величин d(a), d(c), d(g) и d(i), то вершина g окрашивается. Также окрашивается и дуга (a, g), которая и определяет величину d(g). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e), (d, h), (e, f) и (a, g) (рисунок 4 е).

Шаг 3. Поскольку вершина i остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2. (у = g).

d c min d c , d g a g, c min 27, 18 27, d i min d i , d g a g, i min 20, 18 20.

35

Поскольку величина d(i) = 20 является минимальной из величин d(a), d(c),

иd(i) то вершина i окрашивается, что и требуется в задаче. Также окрашивается

идуга (e, i), которая и определяет величину d(i). Текущее дерево кратчайших путей состоит из дуг (a, d), (a, b), (d, e), (d, h), (e, f), (a, g) и (e, i) (рисунок 4 ж).

Суммарное расстояние от вершины a (1) до вершины i (13) составляет 20 км и пролегает через вершины 1, 5, 6, 13. Кроме того, можно отметить, что попутно было определено расстояние от вершины a (1) до вершины f (7), которое составляет 16 км и пролегает через вершины 1, 5, 6, 7.

Кратчайшее расстояние между вершинами 7 и 13 можно определить из треугольника, состоящего из вершин 7, 13 и 6. Кратчайший путь составит 10 км и пролегает через вершины 7, 6, 13.

Аналогично определяем кратчайшие пути между остальными вершинами транспортной сети и заносим их в таблицу 2.1.

Примечание: число пар вершин, между которыми определяются кратчайшие пути, должно быть достаточным для составления транспортной сети между 14 вершинами, указанными в индивидуальном задании.

Таблица 2.1 – Кратчайшие пути между вершинами транспортной сети