4. Между населёнными пунктами A, B, C, D, E, F, G построены дороги. По каждой дороге...

Question

4. Между населёнными пунктами 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