3. Между населёнными пунктами A, B, C, D, E протяжённость которых приведена в таблице: A–B — 1, A–E — 2, B–A — 1, B–D — 1, B–E — 2, C–D — 2, C–E — 1, D–B — 1, D–C — 2, E–A — 2, E–B — 2, E–C — 1. Определите длину кратчайшего пути между пунктами A и C (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.

Проверим возможные краткие пути от A до C. Через E есть дорога A–E длиной 2 и дорога E–C длиной 1, поэтому длина пути A–E–C равна 2 + 1 = 3.

Другой вариант — A–B–D–C: его длина 1 + 1 + 2 = 4. Путь A–B–E–C также имеет длину 1 + 2 + 1 = 4.

Путь A–E–C не повторяет пункты и короче рассмотренных альтернатив.

Ответ: 3.