Граф — точки-вершины и стрелки между ними, у каждой стрелки есть вес, например длина дороги; в файле каждая строка описывает одну стрелку, и вернуться по стрелкам в пройденную вершину нельзя. Повышенный уровень, новая тема 2027 года: нужно программой найти длину кратчайшего пути или число разных путей между двумя вершинами; ответ — число, 1 балл.
Ответ
число в поле ответа
Баллы
1 балл
Проверяет
умение решать алгоритмические задачи на графах: найти кратчайший путь между вершинами и число различных путей в ориентированном графе без циклов
Сколько времени закладывать
около 12 минут по спецификации ФИПИ
Какие бывают подтипы
Кратчайший путь — Найти наименьшую сумму весов на пути из одной вершины в другую и записать её целую часть.
Число разных путей — Посчитать, сколько разных путей ведёт из одной вершины в другую; веса стрелок здесь не нужны.
Пример с полным разбором
Условие. В файле описан граф: каждая строка — стрелка из первой вершины во вторую и её вес. Вернуться по стрелкам в уже пройденную вершину нельзя. Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100; длина пути — сумма весов его стрелок. Для примера — граф из семи стрелок, на экзамене их до двухсот.
Откуда
Куда
Вес
1
2
2.5
1
3
4.0
2
3
1.2
2
5
7.1
3
5
3.6
3
100
9.3
5
100
1.8
Для каждой вершины храним длину лучшего найденного пути до неё из вершины 1. У самой вершины 1 это 0.
Вершины обходим в таком порядке, чтобы все стрелки, входящие в вершину, начинались в уже посчитанных: 1, 2, 3, 5, 100. В графе, где нельзя вернуться в пройденную вершину, такой порядок всегда есть.
До вершины 2 — 2,5. До 3: напрямую 4,0 или через 2: 2,5+1,2=3,7 — берём 3,7.
До 5: через 2 — 2,5+7,1=9,6, через 3 — 3,7+3,6=7,3; берём 7,3.
До 100: через 3 — 3,7+9,3=13,0, через 5 — 7,3+1,8=9,1. Кратчайший путь 1 → 2 → 3 → 5 → 100 длиной 9,1, его целая часть — 9.
Если спрашивают число путей, правило то же, только вместо наименьшего берут сумму: путей в вершину столько, сколько всего путей во все вершины, из которых в неё ведёт стрелка. В этом графе из 1 в 100 ведут 5 путей.
Ответ: 9
Частые ошибки
Округляют длину пути, а нужна целая часть: из 9,7 получается 9, а не 10.
Отбрасывают дробные части весов по дороге, и сумма расходится с верной.
Проходят по стрелке в обратную сторону, хотя она ведёт только из первой вершины во вторую.
Читают вес как целое число, и программа останавливается с ошибкой на записи вида 4.0.
Заводят список на 100 вершин, хотя номера идут не подряд и бывают больше 100.
Что нужно знать для задания 23
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.
Граф: точки, стрелки, веса
Файл задания: одна строка — одно ребро
Кратчайший путь: у каждой вершины своя лучшая сумма
Сколько разных путей: то же движение, другое действие
Да, тематика сменилась в 2027 году: теперь это задачи на графы — оптимальный путь и число путей в ориентированном графе без циклов. Прежнее задание 23 про ход исполнения алгоритма стало заданием 13.
Нужна ли программа?
Да: в файле до двухсот стрелок, и в демоверсии прямо сказано, что для выполнения задания следует написать программу. На задание по спецификации отводится около 12 минут.