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