А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) 9
Решение
1. Построим граф на основе данных таблицы.
Полезный совет. При построении графа не экономьте место — расположите вершины на листе свободно, сами вершины располагайте по кругу и именуйте по порядку по часовой стрелке.
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. Аккуратно вписывайте вес рёбер, чтобы не запутаться, к какому именно ребру он относится.
