9. Найдите кратчайший путь между A и F, проходящий через пункт C. Матрица расстояний: AB = 3, AC = 5, AF = 1, BC = 1, BD = 4, CD = 2, DE = 3, DF = 6, EF = 4, CF = 9.

Кратчайший путь из A в C — прямое ребро A—C длиной 5. Из C в F кратчайший путь — C—D—F длиной 2 + 6 = 8; альтернативный C—F имеет длину 9. Суммарная длина пути через C: 5 + 8 = 13.

Ответ: A—C—D—F, длина пути — 13.