СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


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

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

 

ABCDEF
A157111
B1
C523
D7232
E139
F11329

 

 

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

Решение.

Нарисуем граф.

 

Найдём все пути из A в F.

 

A→C→D→E→F — 19

A→C→D→F —9

A→C→F — 8

A→D→C→F — 12

A→D→E→F —19

A→D→F — 9

A→E→D→C→F — 9

A→E→D→F — 6

A→E→F — 10

A→F — 11

 

Кратчайший путь имеет длину 6.