Задача Задача №3553658
А
А
В таблице представлена информация о стоимости проезда (в рублях) между населёнными пунктами А, Б, В, Г, Д, Е. Если на пересечении столбца и строки пусто, то пункты не соединены…
Запрос пользователя
В таблице представлена информация о стоимости проезда (в рублях) между населёнными пунктами А, Б, В, Г, Д, Е. Если на пересечении столбца и строки пусто, то пункты не соединены дорогой. А Б В Г Д Е А 5 10 14 Б 5 4 10 В 10 3 11 Г 4 4 Д 14 3 19 Е 10 11 4 19 Определите минимальную стоимость проезда от населённого пункта А до населённого пункта Е. Ответ в руб
Задача: найти минимальную стоимость проезда из А в Е.
- Построим граф из таблицы
- 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
(ребра симметричны, пустые пересечения означают отсутствие прямого пути)
- Применим алгоритм Дейкстры (поиск кратчайшего пути в неориентированном графе)
- Начальные расстояния из А: 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.
- Проверим маршрут Из А оптимальный путь: А → Б (5) → Г (4) → Е (4) = 5 + 4 + 4 = 13.
Ответ: 13 руб.
