Через пункт B. №4 ОГЭ
Варианты четвёртого задания ОГЭ, нахождение кратчайшего пути, проходящего или не проходящего через заданный пункт.
№B64486
условие
решение
ответ
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
| A | B | C | D | E | |
| A | 1 | 5 | 2 | ||
| B | 1 | 6 | |||
| C | 5 | 1 | 7 | ||
| D | 6 | 1 | |||
| E | 2 | 7 |
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт B (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Один из возможных вариантов схемы:
По сути, строим взвешенный граф. Удобнее, если дороги не будут пересекаться. Чтобы проще было строить схему, соотношение длин дорог можно не учитывать.
Сначала находим кратчайший путь из начального пункта A до B, затем — кратчайший путь от B до конечного пункта D.
(Обычно, они не проходят через один пункт. Но если так окажется, нужно выбирать по общей длине — какой из этих отрезков пути даст минимальную общую длину).
Кратчайший путь A — B — D. Длина: 1 + 6 = 7
№8323C8
условие
вариант схемы
ответ
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
| A | 3 | 4 | 15 | |||
| B | 3 | 2 | ||||
| C | 4 | 2 | 1 | |||
| D | 1 | 2 | 6 | |||
| E | 2 | 2 | ||||
| F | 15 | 6 | 2 |
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт B. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Длина кратчайшего пути: 4 + 1 + 2 + 2 = 9