"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами…
"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). "
Класс, давай разберёмся вместе.
Что ты дал как ответ: 16, смысл — путь A-B-E-F (2 + 8 + 6 = 16).
Но правильный ответ: 13.
Как это получилось (сокращённо и понятно)
Построим карту дорог (дороги двусторонние):
- A-B = 2
- A-E = 19
- B-E = 8
- B-C = 11
- C-E = 4
- B-D = 3
- D-E = 2
- E-F = 6
Видно, что F можно попасть только через E, а E — из A, B, C, D. Поэтому проверяем все пути до F через E.
Рассмотрим варианты:
- A-E-F: 19 + 6 = 25
- A-B-E-F: 2 + 8 + 6 = 16
- A-B-C-E-F: 2 + 11 + 4 + 6 = 23
- A-B-D-E-F: 2 + 3 + 2 + 6 = 13
Самый короткий путь — A-B-D-E-F, суммарно 13.
Можно привести и краткий путь алгоритма Дейкстры для наглядности:
- старт: A (0); соседи: B=2, E=19
- выбрать B (2); обновления: E=10 (через B), C=13, D=5
- выбрать D (5); обновление E: теперь E=7
- выбрать E (7); попасть в F: F=13
- далее F достигнут за 13, путь A-B-D-E-F
Таким образом, твой ответ 16 неверен — правильный ответ 13.
Пожалуйста, оцени мой ответ лайком или дизлайком.
