№1 Миша идет от школы (Ш) до дома (Д), передвигаясь по дорогам, приведенным в таблице. Число в таблице показывает протяженность дороги между соответствующими точками, а отсутствие числа говорит о том, что дороги нет. Найдите кратчайшую длину пути от школы до дома. Передвигаться можно только по тем дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.

Из таблицы следуют дороги: Ш—К — 3, Ш—О — 5, Ш—А — 8, К—О — 1, К—Д — 6, О—Д — 4, О—А — 2, Д—А — 1.

1. Сравним возможные пути от Ш до Д без повторного посещения пунктов: Ш—К—Д: 3 + 6 = 9.
2. Ш—О—Д: 5 + 4 = 9.
3. Ш—А—Д: 8 + 1 = 9.
4. Через дополнительные пункты путь не короче: например, Ш—К—О—Д имеет длину 3 + 1 + 4 = 8.

Ответ: кратчайшая длина пути — 8; путь Ш—К—О—Д.