Главная / Экзамен / Задание №4
Задание 4 требует найти кратчайший путь между A и Е по заданной таблице дорог. Учебно объясняем, как работать с графами, как учитывать ограничения и как выбрать.
Впишите правильный ответ.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 2 | 1 | |||
| B | 2 | 3 | 3 | ||
| C | 3 | 3 | 2 | ||
| D | 1 | 3 | 3 | ||
| E | 2 |
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Подсказки открываются по одной и не показывают готовый ответ.
В задаче даны пункты A, B, C, D, E и таблица дорог с их расстояниями. Это классический графовый пример: вершины — населённые пункты, рёбра — дороги, веса — расстояния. Нужно определить кратчайший путь между A и Е с условием, что можно двигаться только по дорогам и каждый пункт можно посетить лишь один раз (то есть рассмотреть простые маршруты без повторения вершин). Для начала записываем struktуру графа по таблице: значения без пересечений означают отсутствие дороги в обе стороны, коэффициенты заполняются симметрично, если дорога между двумя пунктами есть. Затем формируем граф: ребра с весами, единичные переходы между соседними пунктами и проверяем все возможные простые пути из A к E. В учебной задаче важно освоить навык чтения таблицы как карты графа, умение извлекать связи между вершинами и оценивать последовательности вершин без повторений.
Экза