А3 кратчайший путь в графе ответы

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

Между населёнными пунктами 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-C-D-F = 13км. Правильный ответ 3.

Чтобы не запутаться, рекомендуется перебирать пункты в алфавитном порядке.

Дополнение (ГИА 2014)

Для более качественной подготовки к ГИА по информатике рассмотрим решение задачи 3 ГИА 2014 по информатике (демоверсия ФИПИ 2014)

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

A	B	C	D	E
A	2	5	1
B	2	1
C	5	1	3	2
D	1	3
E	2

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

1) 4 2) 5 3) 6 4) 7

Решение:

Для удобства предлагаю поступить так же, как и при решении задачи ГИА 2013 года и отобразить таблицу в виде графа. Для этого на листе расставляем точки — населенные пункты. В соответствии с таблицей соединяем их и подписываем расстояния.

Задача 3 ГИА 2014 по информатике

Осталось рассмотреть все возможные маршруты из A в E и найти кратчайший из них. При этом обращаем внимание на то, что в пункт E мы можем попасть только из пункта C.

Как видим, минимальное расстояние — 5 километров (маршрут A-B-C-E). Правильный ответ 2.

Рассмотрим решение задачи из диагностической работы ГИА по информатике 19 декабря 2013 года

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

ИНФ90301 задача 3

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

1) 11 2) 12 3) 13 4) 14

Решение:

Преобразуем таблицу в граф для удобства.

граф к задаче 3

Осталось перебрать все маршруты из A в B и посмотреть их длину:

A-D-C-E-B = 10+1+3+1 = 15

Как видим, минимальный по длине маршрут A-C-E-B, который составляет 12 километров. Правильный ответ 2.

Автор: Александр Чернышов

Оцените статью, это очень поможет развитию сайта.

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

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

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

Из пунк­та A можно по­пасть в пунк­ты B, С.

Из пунк­та B можно по­пасть в пунк­ты C, D.

Из пунк­та C можно по­пасть в пункт D.

Из пунк­та D можно по­пасть в пункт E.

A—B—C—D—E: длина марш­ру­та 13 км.

A—B—D—E: длина марш­ру­та 10 км.

A—C—D—E: длина марш­ру­та 10 км.

A—C—B—D—E: длина марш­ру­та 9 км.

Самый ко­рот­кий путь: A—C—B—D—E. Длина марш­ру­та 9 км.

• Попроси больше объяснений
• Следить
• Отметить нарушение

14.01.2015

Что ты хочешь узнать?

Ответ

Проверено экспертом

Данную задачу можно представить в виде графа для более наглядного решения (см. рисунок 2)
Здесь черные кружки — это пункты
Красные линии — это возможные пути перехода из одного пункта в другой
Если от одного пункта к другому нет линии, значит нельзя перейти о чем в таблице свидетельствует пустая клетка на перекрестье пунктов в таблице.
на рисунке 1 показано как найти расстояние от B до С или от С до B (направление не имеет разницы)

Для задачи с маленьким количеством пунктов (как в примере) можно воспользоваться простым перебором
следуя от пункта А к пункту Е, складывая длины переходов, тем самым можно найти наименьший.

Например (путь A-B-C-E)
2+1+2=5
путь A-D-C-E
1+3+2=5
пусть A-C-E
5+2=7
Отсюда мы видим что минимальный путь равен 5