Задание 4 ОГЭ по информатике: решения ФИПИ с ответами по шагам

Кратчайший путь в графе

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

1. 1
   Рассмотрим маршруты из A в D, не посещая один и тот же пункт повторно.
2. 2
   Маршрут $A \to B \to C \to D$ имеет длину:$$2 + 1 + 5 = 8$$

Ещё 4 шага — в полном решении

Кратчайший путь через C

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

1. 1
   Рассмотрим путь A–C–B–E. Он проходит через C и посещает каждый пункт не более одного раза.$$4 + 2 + 4 = 10$$
2. 2
   Другой возможный путь A–C–D–E имеет длину 12 км. Также возможен путь A–B–C–D–E длиной 17 км. Минимальная длина равна 10 км.$$\min(10, 12, 17) = 10$$

Кратчайший путь в графе

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

1. 1
   Рассмотрим путь A—B—C—D—E—F. Он проходит по всем указанным дорогам и не посещает пункты повторно.$$3+1+1+2+2=9$$
2. 2
   Другие возможные пути имеют большую длину: например, A—C—D—E—F равен $5+1+2+2=10$ км, а прямой путь A—F равен 15 км. Следовательно, кратчайшим является путь через B, C, D и E.$$9<10<15$$

Кратчайший путь в графе

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

1. 1
   Рассмотрим основные маршруты из A в D и сложим длины входящих в них дорог.$$A\text{–}C\text{–}D: 1 + 1 = 2$$
2. 2
   Другие возможные маршруты длиннее: A–B–D имеет длину 7, A–B–C–D — 5, A–E–D — 9.

Ещё 1 шаг — в полном решении

Кратчайший путь в графе

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

1. 1
   Рассмотрим путь B–A–C–D–E. Все необходимые дороги указаны в таблице, и каждый пункт посещается только один раз.$$B\to A\to C\to D\to E$$
2. 2
   Сложим длины дорог этого пути:$$2 + 1 + 1 + 2 = 6$$

Ещё 1 шаг — в полном решении

Кратчайший путь через вершину

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

1. 1
   Рассмотрим допустимый путь A–B–C–D–E–F, проходящий через C. Его длина:$$3+2+1+1+2=9$$
2. 2
   Другой возможный путь A–B–C–E–F имеет длину $3+2+3+2=10$ км. Путь A–B–C–D–E–F короче, поэтому он является кратчайшим.$$9<10$$

Кратчайший путь в графе

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

1. 1
   Рассмотрим возможные маршруты из A в D, не посещая ни один пункт более одного раза.
2. 2
   Для маршрута A–B–E–D длина равна сумме длин дорог A–B, B–E и E–D:$$2 + 1 + 1 = 4$$

Ещё 1 шаг — в полном решении

Кратчайший путь между пунктами

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

1. 1
   Из пункта B есть дорога только в пункт C, поэтому маршрут начинается с перехода B → C длиной 4 км.$$L_{BC}=4$$
2. 2
   Из C можно попасть в A или D. Маршрут через A и D до E имеет длину:$$L_{BCADE}=4+1+2+1=8$$

Ещё 1 шаг — в полном решении