9. В таблице представлена стоимость проезда (в рублях) между станциями метро. Пустая клетка означает, что прямого пути нет. Постройте граф по весовой матрице: A–B — 50, A–C — 120, A–D — нет пути; B–C — 40, B–D — 80; C–D — 30. Какова минимальная стоимость проезда от станции A до станции D? Укажите маршрут.

Строим неориентированный взвешенный граф: вершины — станции, рёбра — прямые пути, числа у рёбер — стоимость проезда.

Сравним маршруты из A в D: A–B–D стоит 50 + 80 = 130 рублей; A–C–D — 120 + 30 = 150 рублей; A–B–C–D — 50 + 40 + 30 = 120 рублей.

Ответ: минимальная стоимость — 120 рублей; маршрут A–B–C–D.