1. Между населёнными пунктами А, В, C, D, Е построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами А и С (при условии, что передвигаться можно только по построенным дорогам).

Решение:

Для нахождения кратчайшего пути между пунктами А и С, будем использовать таблицу расстояний и метод поиска кратчайшего пути (например, алгоритм Дейкстры или просто перебор вариантов, так как количество точек невелико).

Рассмотрим возможные пути из А в С:

• A -> C: Прямой путь. Длина = 2.
• A -> B -> C: Путь через пункт B. Длина = 1 (A->B) + 1 (B->C) = 2.
• A -> D -> C: Путь через пункт D. Длина = 1 (A->D) + 2 (D->C) = 3.
• A -> E -> C: Путь через пункт E. Длина = 2 (A->E) + 1 (E->C) = 3.
• A -> B -> E -> C: Путь через B и E. Длина = 1 (A->B) + 2 (B->E) + 1 (E->C) = 4.
• A -> D -> B -> C: Путь через D и B. Длина = 1 (A->D) + 2 (D->B) + 1 (B->C) = 4.

Сравнивая длины всех возможных путей, находим кратчайший.

Кратчайшие пути имеют длину 2:

• A -> C
• A -> B -> C

Ответ: 2