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