Анализировать простейшие модели объектов · 81 задание
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пункт…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A , B , C , D , E , F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайш…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A | B | C | D | E | |
A | 4 | 2 | 8 | ||
B | 4 | 7 | |||
C | 2 | 7 | 2 | 6 | |
D | 2 | 3 | |||
E | 8 | 6 | 3 |
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
11
Пояснение
Решение. Для решения этой задачи мы построим дерево всех возможных путей из пункта B в пункт E, учитывая условие, что каждый пункт можно посетить только один раз. Это поможет нам наглядно сравнить длины маршрутов и найти кратчайший.
Выпишем все возможные маршруты, начиная из пункта B:
1. Путь через пункт A:
Из B можно поехать в A (длина 4).
- Из A можно поехать в C (длина 2). Из C можно поехать в D (длина 2) или в E (длина 6).
а) Маршрут B — A — C — E: длина 4+2+6=12 км.
б) Маршрут B — A — C — D — E: длина 4+2+2+3=11 км.
- Из A можно поехать сразу в E (длина 8).
в) Маршрут B — A — E: длина 4+8=12 км.
2. Путь через пункт C:
Из B можно поехать в C (длина 7).
- Из C можно поехать в A (длина 2). Но из A мы можем поехать только в E (так как в B возвращаться нельзя).
а) Маршрут B — C — A — E: длина 7+2+8=17 км.
- Из C можно поехать в D (длина 2).
б) Маршрут B — C — D — E: длина 7+2+3=12 км.
- Из C можно поехать сразу в E (длина 6).
в) Маршрут B — C — E: длина 7+6=13 км.
Сравним полученные результаты:
- B — A — C — E: 12 км
- B — A — C — D — E: 11 км
- B — A — E: 12 км
- B — C — A — E: 17 км
- B — C — D — E: 12 км
- B — C — E: 13 км
Самым коротким оказался путь B — A — C — D — E, его длина составляет 11 км.
Ответ: 11 км
Источник: ФИПИ