Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и E.
Реши задание на изображении
Сверь числа и знаки с фото.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
A B C D E F A 2 7 8 B 2 2 1 4 C 7 2 1 D 1 E 1 1 F 8 4 1
Краткий ответ: 5.
Кратчайший маршрут:
\[ A \to B \to C \to E \]
Его длина:
\[ 2+2+1=5 \]
Как это получить
Из пункта \(A\) есть дороги: \[ AB=2,\quad AC=7,\quad AF=8. \] Самый выгодный первый шаг — в \(B\).
Из \(B\): \[ BC=2,\quad BD=1,\quad BF=4. \] Идём в \(C\), получаем расстояние: \[ AB+BC=2+2=4. \]
Из \(C\) есть дорога в \(E\): \[ CE=1. \] Значит, \[ A\to B\to C\to E=4+1=5. \]
Проверим другие варианты:
\[ A\to C\to E=7+1=8, \] \[ A\to B\to F\to E=2+4+1=7, \] \[ A\to F\to E=8+1=9. \]
Все они длиннее 5. Пункт \(D\) соединён только с \(B\), поэтому короткого пути через него к \(E\) нет.
Ответ: 5.
Обсуждение
3 сообщенияОтвет: 3.
Кратчайший маршрут:
\[ A \to D \to E \to F, \qquad 1+1+1=3. \]
Это задание того же типа, что и предыдущее, но в таблице другие числа, поэтому считаем заново.
Ход решения
По таблице (она симметрична) дороги такие:
\[ AB=9,\ AC=2,\ AD=1,\ AE=4,\ AF=5,\ BC=2,\ CD=4,\ DE=1,\ EF=1. \]
Ищем кратчайшие расстояния от \(A\):
| Пункт | Расстояние от \(A\) | Путь |
|---|---|---|
| \(A\) | 0 | — |
| \(D\) | 1 | \(A\to D\) |
| \(C\) | 2 | \(A\to C\) |
| \(E\) | 2 | \(A\to D\to E\) |
| \(F\) | 3 | \(A\to D\to E\to F\) |
| \(B\) | 4 | \(A\to C\to B\) |
Из \(A\) ближе всего \(D\) (1). Из \(D\) за 1 попадаем в \(E\), итого 2 — это выгоднее прямой дороги \(A\to E=4\). Из \(E\) за 1 попадаем в \(F\), итого 3 — выгоднее прямой дороги \(A\to F=5\).
Проверка
Путь короче 3 — это одна дорога или две:
- одна: \(A\to F=5\);
- две: \(A\to E\to F=4+1=5\), а дорог \(A\to D\to F\) и \(A\to C\to F\) нет;
- через \(B\) пройти дальше нельзя — это тупик.
Значит, меньше 3 не получится, а 3 достигается.
Ответ: 3.
