Между населенными пунктами А, В, С, D, E, F построены дороги, протяженность которых (в километрах) приведена в таблице ABCDEF A 2 3 9 15 B 2 6 C 3 5 D 9 6 5 2 11 E 2 3 F 15 11 3 Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, указанным в таблице.

Ищем кратчайший путь из A в F, используя таблицу:

• A → F = 15
• A → B → E → F = 2 + ∞ + ∞ = ∞
• A → B → C → E → F = 2 + ∞ + ∞ + ∞ = ∞
• A → B → D → E → F = 2 + 6 + 2 + 3 = 13
• A → B → D → F = 2 + 6 + 11 = 19
• A → C → D → E → F = 3 + 5 + 2 + 3 = 13
• A → C → D → F = 3 + 5 + 11 = 19
• A → C → E → F = 3 + ∞ + ∞ = ∞
• A → D → E → F = 9 + 2 + 3 = 14
• A → D → F = 9 + 11 = 20

Кратчайшие пути A → B → D → E → F и A → C → D → E → F равны 13.

Ответ: 13