В таблице представлена информация о стоимости проезда (в рублях) между населёнными пунктами А, Б, В, Г, Д, Е. Если на пересечении столбца и строки пусто, то пункты не соединены дорогой. А Б В Г Д Е А 5 10 14 Б 5 4 10 В 10 3 11 Г 4 4 Д 14 3 19 Е 10 11 4 19 Определите минимальную стоимость проезда от населённого пункта А до населённого пункта Е. Ответ в руб

Задача: найти минимальную стоимость проезда из А в Е. 1) Построим граф из таблицы - A-B = 5 - A-V = 10 - A-D = 14 - B-G = 4 - B-E = 10 - V-D = 3 - V-E = 11 - G-E = 4 - D-E = 19 (ребра симметричны, пустые пересечения означают отсутствие прямого пути) 2) Применим алгоритм Дейкстры (поиск кратчайшего пути в неориентированном графе) - Начальные расстояния из А: d(A)=0, d(B)=5, d(V)=10, d(D)=14, d(G)=∞, d(E)=∞. - Выбираем ближайшую не посещённую вершину: B (5). - Обновляем: d(G)=min(∞, 5+4)=9; d(E)=min(∞, 5+10)=15. - Следующая ближняя: G (9). - Обновляем: d(E)=min(15, 9+4)=13. - Следующая ближняя: V (10). - Обновляем: d(D)=min(14, 10+3)=13. - d(E)=min(13, 10+11)=13 (уже не лучше). - Следующая ближняя: E и D обе имеют 13. Этап можно завершить, ответ уже известен: путь до Е стоит 13. 3) Проверим маршрут Из А оптимальный путь: А → Б (5) → Г (4) → Е (4) = 5 + 4 + 4 = 13. Ответ: 13 руб.