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