Указаны 5 населенных пунктов: a, b, c, d, e и расстояния между ними в км внутри скобок: a-b(2), a-c(4), b-c(1), b-e(7), c-d(3), c-e(5), b-e(7), d-e(3). самый короткий маршрут из a до e равен а) 3 км в) 7 км с) 8 км d) 9 км
Будем выкидывать заведомо не самые короткие пути. 1) Можно выкинуть AC (4): из A в C можно попасть по ABC за 2 + 1 = 3 2) Можно выкинуть CDE (3 + 3 = 6): из C в E можно попасть по CE за 5
Осталось только два пути: ABE (2 + 7 = 9) и ABCE (2 + 1 + 5 = 8). Выгоднее, конечно, второй.
Будем выкидывать заведомо не самые короткие пути.
1) Можно выкинуть AC (4): из A в C можно попасть по ABC за 2 + 1 = 3
2) Можно выкинуть CDE (3 + 3 = 6): из C в E можно попасть по CE за 5
Осталось только два пути: ABE (2 + 7 = 9) и ABCE (2 + 1 + 5 = 8). Выгоднее, конечно, второй.
c) 8 км