Question

ПОМОГИТЕ ДАМ 20 БАЛОВ
Между населёнными пунк­та­ми A, B, C, D, E, F по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых при­ве­де­на в таб­ли­це. (От­сут­ствие числа в таб­ли­це озна­ча­ет, что пря­мой до­ро­ги между пунк­та­ми нет.)



A B C D E F
A 3
B 9 4
C 3 9 3 8
D 3 2
E 4 8 2 7
F 7

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и F (при усло­вии, что пе­ре­дви­гать­ся можно толь­ко по по­стро­ен­ным до­ро­гам).

Answer 1

Находим все возможные варианты
В пункт F можно по­пасть толь­ко из пунк­та Е.
В пункт Е можно по­пасть из пунк­тов С, В и D.

В пунк­ты В и D можно по­пасть толь­ко из пунк­та С.

В пункт С можно по­пасть толь­ко из пунк­та А.

 A-C-E-F. Длина марш­ру­та 3 + 8 + 7 = 18.

 A-С-D-E-F. Длина марш­ру­та 3 + 3 + 2 + 7 = 15.

 A-С-B-E-F. Длина марш­ру­та 3 + 9 + 4 + 7 = 23.

 Видно, что крат­чай­ший путь равен 15.