Разбор задачи A2 (демо ЕГЭ 2012)
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 4 | ||||
| B | 2 | 1 | 7 | |||
| C | 4 | 1 | 3 | 4 | ||
| D | 3 | 3 | ||||
| E | 7 | 4 | 3 | 2 | ||
| F | 2 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
- 9
- 10
- 11
- 12
Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.
Нарисуем путь из пункта А в F. Начнем с конца, с пункта F. В него идет дорога из Е:
В пункт Е ведут дороги из D, C и B:
В пункт D ведет дорога из С, в пункт С ведет дорога из В, в пункт В ведет дорога из А:
В пункт С ведет дорога из В, в пункт В ведет дорога из А:
В пункт В ведет дорога из А:
Видим, что из А в F ведет 3-и пути. Надо найти кратчайший путь из трех. Добавим в граф значение расстояний между пунктами:
1-й путь: A-B-C-D-E-F=2+1+3+3+2=11
2-й путь: A-B-C-E-F=2+1+4+2=9
3-й путь: A-B-E-F=2+7+2=11
Получили кратчайший путь: A-B-C-E-F. Его длина равна 9.