Подготовка к OГЭ: Задание 3

Задача 3.

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

A

B

C

D

E

F

A

3

5

15

B

3

3

C

5

3

5

2

D

5

3

E

2

7

F

15

3

7

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

1) 9 2) 11 3) 13 4) 15

Решение

Для удобства отобразим табличные данные в виде графа

Решение задачи 2 ГИА по информатике

Теперь переберем все возможные пути из A в F:

A-B-C-E-F = 3+3+2+7 = 15

A-B-C-D-F = 3+3+5+3 = 14

A-C-E-F = 5+2+7 = 14

A-C-D-F = 5+5+3 = 13

ну и A-F = 15

Как видно, кратчайший вариант A-C-D-F = 13км.

Правильный ответ 3.