1.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых в (километрах) приведена в таблице.
Реши задание на изображении
Сверь числа и знаки с фото.
1.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых в (километрах) приведена в таблице.
A B C D E F A 3 4 15 B 3 2 C 4 2 1 D 1 2 6 E 2 2 F 15 6 2 Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт B. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
2.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице:
A B C D E F A 2 1 B 1 3 C 2 1 4 D 1 1 4 E 1 5 F 3 4 4 5 Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Краткий ответ:
- 9 км — путь \(A \to C \to D \to E \to F\).
- 5 км — путь \(A \to D \to F\).
Как рассуждать
Таблица симметрична: число на пересечении строки и столбца показывает длину дороги между пунктами. Нужно выбрать путь с наименьшей суммой длин дорог.
Задание 1. Пункт \(B\) проходить нельзя.
Считаем возможные пути:
\[ A \to C \to D \to E \to F: 4+1+2+2=9 \]
Другие варианты длиннее:
\[ A \to C \to D \to F: 4+1+6=11 \]
\[ A \to F:\ 15 \]
Значит, кратчайший путь — 9 км.
Задание 2. Используем дороги из таблицы:
\[ A-D=1,\quad A-C=2,\quad B-C=1, \] \[ B-F=3,\quad C-F=4,\quad D-E=1, \] \[ D-F=4,\quad E-F=5. \]
Проверяем пути:
\[ A \to D \to F: 1+4=5 \]
\[ A \to C \to F: 2+4=6 \]
\[ A \to C \to B \to F: 2+1+3=6 \]
\[ A \to D \to E \to F: 1+1+5=7 \]
Минимальная длина — 5 км, путь \(A \to D \to F\).
