Задание 4. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

По таблице дороги имеют длины: A—B — 2, A—C — 5, A—F — 9, B—C — 2, B—D — 1, B—F — 5, C—E — 1, E—F — 1.

Рассмотрим основные пути от A до F:

• A—F: 9;
• A—B—F: 2 + 5 = 7;
• A—C—E—F: 5 + 1 + 1 = 7;
• A—B—C—E—F: 2 + 2 + 1 + 1 = 6;
• A—B—D: путь до F по имеющимся дорогам требует возврата через B, поэтому короче пути длиной 6 не получается.

Кратчайший путь — A—B—C—E—F, его длина равна 6.

Ответ: 6.