Решение

В

а)

	А

Рис. 11

Превращаем граф в нагруженный, подставляя веса ребер слева направо (по оси Ox) и снизу вверх (по оси Oy) (рис. 11);

б) действуем по алгоритму: вершине А приписываем индекс 0, остальным вершинам + . Вершины, смежные с А, получают новые индексы: вершина (0; 1): 0 + 9 = 9, вершина (1; 0): 0 + 7 = 7. Вершина (1; 1) может получить индекс 7 + 4 = 11 или 9 + 6 = 15. выбираем наименьший из возможных индексов – 11 (рис 12).

Рис 12

Действуя аналогичным образом, присваиваем новые индексы всем вершинам. При этом вершина В получает индекс 27 (рис. 13).

Рис. 13

Индекс 27 = 26 + 1, следовательно, из вершины В нужно идти вниз, в вершину (4; 3) с индексом 26. 26 = 25 + 1, из вершины (4; 3) переходим в вершину (3; 3) с индексом 25. Этот индекс может быть получен двумя способами: 25 = 23 + 2 = 18 + 7, т.е. получаем два пути. 18 = 17 + 1, 23 = 17 + 6; оба пути сходятся в вершине (2; 2). 17 = 16 + 1; 16 = 11 + 5; 11 = 7 + 4; 7 = 0 + 7.

мы вернулись в вершину А. Таким образом, построены два пути с наименьшей суммой весов, равной 27 (рис. 14).

Рис. 14

Вот эти пути:
(0; 0) – (0; 1) - (1; 1) - (1; 2) – (2; 2) – (2; 3) – (3; 3) – (3; 4) – (4; 4)

и
(0; 0) – (0; 1) - (1; 1) - (1; 2) – (2; 2) – (3; 2) – (3; 3) – (3; 4) – (4; 4).

Дата добавления: 2014-11-20