Задание №4 — Теоретические основы информатики
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A | B | C | D | E | F | |
A | 2 | 3 | 7 | 15 | ||
B | 2 | 3 | ||||
C | 3 | 5 | ||||
D | 7 | 3 | 5 | 2 | 11 | |
E | 2 | 4 | ||||
F | 15 | 11 | 4 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
11
Пояснение
Решение. Для поиска кратчайшего пути между пунктами A и F удобно использовать метод построения дерева возможных маршрутов или схематичного графа. Выпишем все возможные связи между пунктами, указанные в таблице:
A связан с: B (2 км), C (3 км), D (7 км), F (15 км).
B связан с: A (2 км), D (3 км).
C связан с: A (3 км), D (5 км).
D связан с: A (7 км), B (3 км), C (5 км), E (2 км), F (11 км).
E связан с: D (2 км), F (4 км).
F связан с: A (15 км), D (11 км), E (4 км).
Теперь рассмотрим все возможные пути из A в F, учитывая условие, что каждый пункт можно посетить только один раз:
1) Прямой путь: A → F
Длина: км.
2) Пути через пункт D:
• A → D → F: км.
• A → B → D → F: км.
• A → C → D → F: км.
3) Пути через пункт E (который связан с D и F):
• A → D → E → F: км.
• A → B → D → E → F: км.
• A → C → D → E → F: км.
Сравним полученные результаты: , , , , , , .
Самым коротким является маршрут A → B → D → E → F, длина которого составляет км.
Ответ: 11 км
Источник: ФИПИ