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