Кратчайший путь по таблице. Между населёнными пунктами A, B, C, D построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами D и B. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.

Из таблицы: D–A — 3, D–C — 6, A–B — 5, A–C — 2, B–C — 1. Дороги D–B и B–D в таблице не указаны.

1. Прямого пути D–B нет, поэтому сравним маршруты через другие пункты.
2. Путь D–A–C–B проходит по указанным дорогам и не повторяет пункты: 3 + 2 + 1 = 6.
3. Например, путь D–C–B имеет длину 6 + 1 = 7; путь D–A–B — 3 + 5 = 8. Другие допустимые маршруты не короче.

Ответ: кратчайший путь — D–A–C–B, его длина 6.