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

Решение:

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

Представим граф дорог:

• A-B: 5
• A-C: 9
• A-D: 5
• A-G: 17
• B-C: 2
• C-D: 3
• C-E: 2
• D-E: (нет прямого пути)
• E-F: 4
• E-G: 6
• F-G: 1

Будем искать кратчайший путь от А до G, отслеживая минимальные расстояния до каждого города:

1. Из А:
• A → A: 0
• A → B: 5
• A → C: 9
• A → D: 5
• A → G: 17
2. Из В (расстояния из А):
• B → C: 5 + 2 = 7. Так как 7 < 9, обновляем расстояние до C: A → B → C = 7.
3. Из С (расстояния из А):
• C → D: 7 + 3 = 10. Так как 10 > 5 (A → D), расстояние до D не меняется.
• C → E: 7 + 2 = 9.
4. Из D (расстояния из А):
• D → C: 5 + 3 = 8. Так как 8 > 7 (A → B → C), расстояние до C не меняется.
• D → E: (нет прямого пути, но мы можем идти через C, тогда 5 + 3 + 2 = 10 до E)
5. Из Е (расстояния из А):
• E → C: 9 + 2 = 11. Так как 11 > 7, расстояние до C не меняется.
• E → G: 9 + 6 = 15. Так как 15 < 17 (A → G), обновляем расстояние до G: A → B → C → E → G = 15.
• E → F: 9 + 4 = 13.
6. Из F (расстояния из А):
• F → E: 13 + 4 = 17. Так как 17 > 9, расстояние до E не меняется.
• F → G: 13 + 1 = 14. Так как 14 < 15, обновляем расстояние до G: A → B → C → E → F → G = 14.

Кратчайший путь от А до G: A → B → C → E → F → G.

Длина этого пути: 5 + 2 + 2 + 4 + 1 = 14.

Ответ: 14