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