А3. Теория графов — нахождение кратчайшего пути.

Пример задания

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.

A B C D E F
A 3 5 15
B 3 4
C 5 1
D 4 1 2 6
E 2 1
F 15 6 1

Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице.

1) 9 2) 11 3) 13 4) 15

Решение

1. Построим граф на основе данных таблицы.

Полезный совет. При построении графа не экономьте место — расположите вершины на листе свободно, сами вершины располагайте по кругу и именуйте по порядку по часовой стрелке.

gr1

2. Давайте посмотрим, какие вообще существуют пути из А в F.

Первый вариант: А — F = 15

Второй вариант: путь через прочие вершины, как видно из схемы, в любом случае будет проходить через вершину D  — тогда первый этам — нахождение кратчайшего пути до D.

A — B — D = 3 + 4 = 7

A — C — D = 5 + 1 = 6 (min!)

От D до F также можно пройти двумя путями:

D — F = 6

D — E — F = 2 + 1 = 3 (min!)

Суммируем полученные минимальные пути: 6 + 3 = 9.

Итого, кратчайший путь равен 9 и проходит через вершины A — C — D — E — F

На что нужно обратить внимание

1. При построении графа на основе табличных данных пересчитайте количество рёбер — оно должно соответствовать количеству цифр в таблице выше или ниже диогонали.

2. Аккуратно вписывайте вес рёбер, чтобы не запутаться, к какому именно ребру он относится.