Определите длину кратчайшего маршрута между пунктами А и В. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего маршрута между пунктами А и В. Передвигаться можно только по указанным дорогам.
Ответ:
Решение:
А имеет 2 дороги — это П6, и В имеет 4 дороги — это П5.
А (П6) идет к В (П5) и Б (П1).
E имеет только одну дорогу (П3), и идет к Д из 3-х дорог (П4).
Г — П2.
AB = 17
АБВ = 5+ 8 = 13
АБГВ = 5 + 10 + 12 ..
АБГДВ = 5 + 10 + 12 +..
Ответ: 13