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