Задача Задача №3777743
А
А
Построй граф для 1 задания
Сверь числа и знаки с фото.
- Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
A B C D E A 6 1 4 B 6 2 5 C 2 2 D 1 5 2 6 E 4 6 Ответ: 9
Краткий ответ: граф неориентированный, его рёбра:
| Ребро | Длина, км |
|---|---|
| \(A-B\) | 6 |
| \(A-D\) | 1 |
| \(A-E\) | 4 |
| \(B-C\) | 2 |
| \(B-D\) | 5 |
| \(C-D\) | 2 |
| \(D-E\) | 6 |
Схема графа:
A
/ | \
6 / |1 \ 4
/ | \
B | E
|\ | /
2 | \5 | / 6
| \ | /
C---D
2
Кратчайший путь от \(B\) до \(E\):
\[ B \to C \to D \to A \to E \]
Его длина:
\[ 2+2+1+4=9 \]
Ответ: 9 км.
Проверка по шагам: из \(B\) до \(C\) — 2 км, затем до \(D\) — ещё 2 км, затем короткий участок \(D-A\) — 1 км и \(A-E\) — 4 км. Другие пути дают 10 км или больше.
