≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 3 № 3487

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

 

ABCDEF
A143
B45
C421
D122
E41
F352

 

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

Пояснение.

Найдём все варианты маршрутов из A в B и выберем самый короткий.

 

В пункт B можно попасть из пунктов С и F.

В пункт F можно попасть из пунктов А и D.

В пункт С можно попасть из пунктов D и Е.

В пункты D и Е можно попасть из пункта А.

 

A-D-C-B. Длина маршрута 1 + 2 + 4 = 7.

 

A-E-C-B. Длина маршрута 4 + 1 + 4 = 9.

 

A-F-B. Длина маршрута 3 + 5 = 8.

 

A-D-F-B. Длина маршрута 1 + 2 + 5 = 8.

 

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