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