Question

Даю 15 баллов,задача изи​

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Answer 1

Ответ:

Длина пути во взвешенном (связном) графе — это сумма длин (весов) тех рёбер, из которых состоит путь.

У нас три пути: ABEF, ABCEF и ABDEF. Определим каждую длину пути:

ABEF: 3+7+3=13

ABCEF: 3+7+5+3=18

ABDEF: 3+4+3+2=12

Таким образом, кратчайший путь – ABDEF, равный 12.

Ответ: 2