Кратчайший путь по таблице расстояний

В задании 4 дороги между пунктами записаны таблицей, и нужно найти длину самого короткого пути из одного пункта в другой. Трудность одна: не пропустить путь, который длиннее по числу дорог, но короче по километрам.

На странице

Теория
Решённые примеры: 4
Типичные ошибки
Где встречается на экзамене
Вопросы и ответы

Теория

Как читать таблицу

Строки и столбцы подписаны названиями пунктов. Число на пересечении строки A и столбца B — длина дороги между A и B.
Пустая клетка значит, что прямой дороги между этими пунктами нет.
Таблица симметрична: дорога из A в B та же, что из B в A. Достаточно читать её половину — выше или ниже диагонали.
На диагонали пусто: дороги из пункта в него самого нет.

В спецификации такая таблица называется весовой матрицей графа: пункты — вершины, дороги — рёбра, длина дороги — вес ребра.

Перерисуй таблицу в схему

Поставь точки-пункты и для каждой заполненной клетки половины таблицы проведи линию с числом. Проверка: линий на схеме должно быть столько же, сколько заполненных клеток в половине таблицы. Расположение точек значения не имеет, длины линий на рисунке — тоже: важны только числа.

Перебор путей без пропусков

Выпиши соседей начального пункта. Для каждого соседа по очереди продолжай путь к конечному пункту.
В один пункт дважды не заезжай: в демоверсии 2027 года прямо сказано, что каждый пункт можно посетить только один раз.
Рядом с каждым путём записывай сумму длин его дорог.
Если сумма уже не меньше лучшего найденного результата, эту ветку можно не продолжать: длины дорог положительны, короче она не станет.
Ответ — наименьшая из сумм.

Способ с пометками

Можно обойтись без перебора всех путей. У начального пункта напиши 0. У каждого его соседа — длину дороги до него. Дальше каждый раз бери ещё не обработанный пункт с наименьшей пометкой и пробуй улучшить пометки его соседей: если «пометка пункта + длина дороги» меньше того, что написано у соседа, исправь число. Когда обработаны все пункты, пометка конечного пункта — длина кратчайшего пути.

Путь через заданный пункт

Если путь из A в F должен пройти через D, раздели его на две части: от A до D и от D до F. Найди кратчайший путь для каждой части и сложи длины. После этого проверь, что части не проходят через один и тот же пункт: если проходят, такой путь заезжает в него дважды, и нужно сравнить другие сочетания.

Решённые примеры

Примеры взяты из тренажёра: там такие же задания, только числа и слова каждый раз новые.

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

Форма демоверсии 2027 года. Прямая дорога между пунктами есть, но она не самая короткая.

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

	A	B	C	D	E	F
A		2	6	1		10
B	2		1		2
C	6	1				7
D	1				9
E		2		9		3
F	10		7		3

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

Решение

Нарисуй схему по таблице — так пути виднее. Дороги: A–B — 2, A–C — 6, A–D — 1, A–F — 10, B–C — 1, B–E — 2, C–F — 7, D–E — 9, E–F — 3.
Выпиши пути из A в F и сложи длины дорог на каждом: A–B–E–F: 2 + 2 + 3 = 7; A–F: 10; A–B–C–F: 2 + 1 + 7 = 10; A–C–B–E–F: 6 + 1 + 2 + 3 = 12. Остальные пути длиннее.
Самый короткий путь — A–B–E–F, его длина 7

Ответ: 7

Можно иначе. Можно не перебирать пути, а идти от пункта A и подписывать у каждого пункта самое короткое расстояние до него: A — 0, D — 1, B — 2, C — 3, E — 4, F — 7. Число у пункта F и есть ответ: 7.

Если получилось другое число

10 — Прямая дорога A–F есть, но путь через другие пункты короче. Сравни несколько путей.
20 — Это длина пути A–D–E–B–C–F. Если на каждом шаге выбирать самую короткую дорогу, весь путь не обязательно получится кратчайшим.

Решать такие же в тренажёре →

2. Когда прямой дороги нет

Из начального пункта выходит одна дорога, поэтому перебор начинается со второго шага.

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

	A	B	C	D	E
A				9
B			9		2
C		9		1	7
D	9		1		9
E		2	7	9

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

Решение

Нарисуй схему по таблице — так пути виднее. Дороги: A–D — 9, B–C — 9, B–E — 2, C–D — 1, C–E — 7, D–E — 9.
Выпиши пути из A в E и сложи длины дорог на каждом: A–D–C–E: 9 + 1 + 7 = 17; A–D–E: 9 + 9 = 18; A–D–C–B–E: 9 + 1 + 9 + 2 = 21.
Самый короткий путь — A–D–C–E, его длина 17

Ответ: 17

Можно иначе. Можно не перебирать пути, а идти от пункта A и подписывать у каждого пункта самое короткое расстояние до него: A — 0, D — 9, C — 10, E — 17, B — 19. Число у пункта E и есть ответ: 17.

Если получилось другое число

18 — Это длина пути A–D–E. Есть путь короче — перебери остальные.

Решать такие же в тренажёре →

3. Путь через заданный пункт

Сравни все пути, которые заходят в обязательный пункт, или раздели путь на две части.

	A	B	C	D	E	F
A		9		6	2	14
B	9		1	6	4
C		1			9	5
D	6	6				9
E	2	4	9
F	14		5	9

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

Решение

Нарисуй схему по таблице — так пути виднее. Дороги: A–B — 9, A–D — 6, A–E — 2, A–F — 14, B–C — 1, B–D — 6, B–E — 4, C–E — 9, C–F — 5, D–F — 9.
Выпиши пути из A в F, которые проходят через D, и сложи длины дорог на каждом: A–D–F: 6 + 9 = 15; A–D–B–C–F: 6 + 6 + 1 + 5 = 18; A–E–B–D–F: 2 + 4 + 6 + 9 = 21; A–B–D–F: 9 + 6 + 9 = 24. Остальные пути длиннее.
Самый короткий из них — A–D–F, его длина 15

Ответ: 15

Можно иначе. Раздели путь на две части. Кратчайший путь от A до D — A–D, это 6. Кратчайший путь от D до F — D–F, это 9. Общих пунктов, кроме D, у них нет, поэтому их можно соединить: 6 + 9 = 15.

Если получилось другое число

12 — Путь A–E–B–C–F короче, но через пункт D он не проходит.
18 — Это длина пути A–D–B–C–F. Через пункт D есть путь короче.
6 — Это только путь от A до D. Осталось доехать от D до F.

Решать такие же в тренажёре →

4. Через пункт, до которого нет прямой дороги

Обе части пути состоят из нескольких дорог; проверь, что у них нет общих пунктов, кроме обязательного.

	A	B	C	D	E	F
A			7			17
B			4	7		7
C	7	4		4	1
D		7	4		4
E			1	4		4
F	17	7			4

Решение

Нарисуй схему по таблице — так пути виднее. Дороги: A–C — 7, A–F — 17, B–C — 4, B–D — 7, B–F — 7, C–D — 4, C–E — 1, D–E — 4, E–F — 4.
Выпиши пути из A в F, которые проходят через D, и сложи длины дорог на каждом: A–C–D–E–F: 7 + 4 + 4 + 4 = 19; A–C–D–B–F: 7 + 4 + 7 + 7 = 25; A–C–B–D–E–F: 7 + 4 + 7 + 4 + 4 = 26; A–C–E–D–B–F: 7 + 1 + 4 + 7 + 7 = 26.
Самый короткий из них — A–C–D–E–F, его длина 19

Ответ: 19

Можно иначе. Раздели путь на две части. Кратчайший путь от A до D — A–C–D, это 11. Кратчайший путь от D до F — D–E–F, это 8. Общих пунктов, кроме D, у них нет, поэтому их можно соединить: 11 + 8 = 19.

Если получилось другое число

12 — Путь A–C–E–F короче, но через пункт D он не проходит.
25 — Это длина пути A–C–D–B–F. Через пункт D есть путь короче.
11 — Это только путь от A до D. Осталось доехать от D до F.

Решать такие же в тренажёре →

Типичные ошибки

Берут длину прямой дороги и не сравнивают её с путями через другие пункты.
Теряют дорогу, когда перерисовывают таблицу в схему: сверь число линий с числом заполненных клеток в половине таблицы.
Считают одну дорогу дважды — по клетке выше диагонали и по клетке ниже.
Останавливаются на первом найденном коротком пути.
В задаче «через пункт» дают в ответ кратчайший путь вообще, хотя он обязательный пункт обходит.
Записывают в ответ путь буквами. Нужна его длина — число.

Где встречается на экзамене

Задание 4 — длина кратчайшего пути по таблице.
Задание 9 — тоже граф, но считают число путей по стрелкам.

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

Вопросы и ответы

Как найти кратчайший путь по таблице?

Перерисовать таблицу в схему, выписать пути от начального пункта к конечному, сложить длины дорог на каждом и выбрать наименьшую сумму.

Что значит пустая клетка в таблице?

Прямой дороги между этими пунктами нет: доехать можно только через другие пункты.

Почему числа в таблице повторяются?

Таблица симметрична: одна и та же дорога записана дважды — из A в B и из B в A.

Что записывать в ответ?

Число — длину кратчайшего пути. Сам путь буквами записывать не нужно.

Соседние темы

Узнай, какие задания уже получаютсяКороткая диагностика по первой части занимает пять минут. После неё — план на каждый день до экзамена.

Пройти диагностику

Теория — школьная программа 7–9 классов; задания составлены нами, числа и слова в тренажёре каждый раз новые. Факты об экзамене — из демоверсии, спецификации и кодификатора ФИПИ для ОГЭ 2027 года; на день обновления документы опубликованы как проект. Обновлено 11.10.2026.