Задание 23
Анализ графов
Граф из файла, кратчайший путь в ациклическом графе рекурсией с запоминанием, обязательные и запрещённые вершины.
6 подтем · 32 задачи + 5 дополнительных · повышенный · ≈ 12 мин
Подтема 1 из 6
Граф и путь
Что спрашивают в задании 23: строка файла — стрелка с весом, путь и его длина, почему в графе нет циклов.
Как устроена тема
В задании 23 дают текстовый файл. В каждой его строке — откуда можно перейти, куда и сколько стоит переход. Нужно найти самый дешёвый маршрут между двумя вершинами. Вот задача, которую мы решим в этой теме:
«В текстовом файле 23-5.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.»
Всё задание — про одно: найти в графе из файла путь с наименьшей суммой весов и записать целую часть этой суммы. Разберём условие:
| В условии | Что это значит |
|---|---|
| ориентированный граф | у ребра есть направление: строка «1 7 5.5» пускает из 1 в 7, но не обратно |
| взвешенный | у каждого ребра есть вес — цена перехода |
| ациклический | двигаясь по стрелкам, нельзя вернуться туда, где уже был |
| в строке L, M и W | ребро из L в M весом W; одна строка — одно ребро, заголовка в файле нет |
| длина кратчайшего пути | наименьшая сумма весов, а не наименьшее число рёбер |
| вершины пронумерованы не подряд | номер — только имя: вершина 100 не значит, что вершин сто |
| целая часть | дробную часть отбрасывают у итоговой суммы, а не у каждого веса |
| пробелы и/или табуляции | строку разбивают line.split() без аргумента: он съедает любые пробелы |
Сначала разберёмся на графе из восьми рёбер, который можно посчитать руками, потом напишем программу и решим задачу из файла. Тема состоит из пяти подтем и дополнительного урока — у каждой своя страница. Идём по ним по порядку:
- Граф и путь — ты сейчас здесь: ребро, путь и его длина.
- Лучший путь до цели — как найти кратчайший путь, не перебирая все.
- Программа с @cache — то же на Python; решим задачу темы: ответ 10211.
- Условия на путь — через вершину, в обход вершины, через ребро.
- Другие вопросы о путях — число путей, самый длинный путь, число рёбер.
- Условие на число рёбер — дополнительный урок: пути ровно из k рёбер.
Ребро и вес
Что значит строка 1 7 5.5?
Из вершины 1 можно перейти в вершину 7, и этот переход стоит 5.5. Такой переход называют ребром, а 5.5 — его весом. Обратно, из 7 в 1, эта строка не пускает: для этого нужна своя строка 7 1 …. На рисунке ребро — стрелка, вес подписан на ней.
Возьмём файл из восьми строк — его приводят как пример в условиях задания 23. На этом графе проверим каждый шаг темы:
100 12 1.06 7 7.06 1 1.01 7 5.57 100 2.04 100 8.01 100 12.01 4 2.5Нарисуем его: каждая строка — стрелка от первого числа ко второму.
Номер вершины — только её имя. Вершин здесь шесть, хотя есть номер 100. И номера не обязаны расти по стрелкам: рёбра 100 → 12 и 6 → 1 ведут к меньшим номерам. Из 12 не выходит ни одной стрелки — дальше этой вершины идти некуда.
Путь и его длина
Как попасть из 1 в 100 и сколько это стоит?
Путь — цепочка стрелок, где каждая начинается там, где кончилась предыдущая. Длина пути — сумма весов его рёбер. Из 1 в 100 ведут три пути:
| Путь | Длина |
|---|---|
| 1 → 100 | 12.0 |
| 1 → 7 → 100 | 5.5 + 2.0 = 7.5 |
| 1 → 4 → 100 | 2.5 + 8.0 = 10.5 |
Кратчайший — 1 → 7 → 100 длиной 7.5. В ответ задания пошла бы его целая часть: 7.
Число рёбер и длина — разные вещи: путь из одного ребра проиграл пути из двух. Пройди по графу сам: нажимай вершины по очереди, начиная с 1. Схема пропустит только ходы по стрелкам и посчитает длину.
Попробуй пойти против стрелки или найти путь короче 7.5 — не выйдет.
Без циклов
Зачем в условии слово «ациклический»?
Оно значит, что по стрелкам нельзя вернуться в вершину, где уже был. Поэтому любой путь когда-нибудь кончается, а путей — конечное число. Если бы в файле была ещё строка 100 1 …, можно было бы ходить по кругу 1 → 7 → 100 → 1 → … без конца. Такой круг называют циклом.
Треугольник на рисунке — ещё не цикл. В учебном графе стрелки 1 → 7, 7 → 100 и 1 → 100 тоже образуют треугольник, но вернуться по ним в 1 нельзя. Цикл идёт только по направлению стрелок.
Без циклов путь из любой вершины либо доходит до цели, либо упирается в тупик — как в вершину 12. На этом держится всё решение следующих подтем.
Итого
- Строка «a b w»ребро из a в b весом w; обратно — только своей строкой
- Номер вершиныимя, а не количество вершин и не порядок
- Путьстрелки цепочкой: каждая из конца предыдущей
- Длина путисумма весов, а не число рёбер
- Ациклический графпо стрелкам не вернуться; любой путь конечен
- Учебный примеркратчайший путь 1 → 7 → 100, длина 7.5, ответ 7
Проверьте себя
Ответь сначала сам, потом открой ответ.
80 12 4.7. Можно ли перейти из 80 в 12? А из 12 в 80?ОтветСкрыть ответ
12 80 ….ОтветСкрыть ответ
ОтветСкрыть ответ
2 9 1.5, 9 4 2.0, 4 2 0.5 и 9 6 3.0. Ациклический ли это граф?ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Посчитайте вершины графа
Сколько вершин в графе с рёбрами 1 → 40, 40 → 7, 7 → 100 и 1 → 100?
Введите число.
Подсказка
Выпиши все разные номера из рёбер. Номер 100 — имя вершины, а не их количество.
Решение
4: вершины 1, 40, 7 и 100.
Решение программой
edges = [(1, 40), (40, 7), (7, 100), (1, 100)]print(len({x for e in edges for x in e}))Ответ: 4
Кратчайший путь перебором
Граф задан рёбрами:
1 20 2.41 7 6.020 7 1.37 100 3.220 100 8.01 100 15.0Выпиши все пути из 1 в 100 и их длины. Запиши в ответ целую часть длины кратчайшего пути.
Введите целую часть найденной длины.
Подсказка
Путей из 1 в 100 четыре. Сложи веса рёбер каждого.
Решение
6: пути стоят 15.0, 9.2, 10.4 и 6.9; кратчайший — 1 → 20 → 7 → 100, 2.4 + 1.3 + 3.2 = 6.9.
Решение программой
from functools import cache EDGES = """1 20 2.41 7 6.020 7 1.37 100 3.220 100 8.01 100 15.0"""graph = {}for line in EDGES.splitlines(): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef f(v, t): if v == t: return 0 best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, t)) return best print(int(f(1, 100)))Ответ: 6
Сколько путей из 6
Учебный граф темы — файл из восьми строк:
100 12 1.06 7 7.06 1 1.01 7 5.57 100 2.04 100 8.01 100 12.01 4 2.5Сколько разных путей ведёт из вершины 6 в вершину 100?
Введите число.
Подсказка
Из 6 можно пойти в 7 или в 1. Выпиши пути через каждую.
Решение
4: 6 → 7 → 100, 6 → 1 → 100, 6 → 1 → 7 → 100 и 6 → 1 → 4 → 100.
Решение программой
from functools import cache EDGES = """100 12 1.06 7 7.06 1 1.01 7 5.57 100 2.04 100 8.01 100 12.01 4 2.5"""graph = {}for line in EDGES.splitlines(): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef count(v, t): if v == t: return 1 total = 0 for u, w in graph.get(v, []): total += count(u, t) return total print(count(6, 100))Ответ: 4
Кратчайший путь в небольшом графе
Граф задан рёбрами:
1 12 3.41 5 6.112 5 1.912 30 7.25 30 2.65 100 9.830 100 4.71 100 16.5Найди длину кратчайшего пути из вершины 1 в вершину 100. В ответ запиши её целую часть.
Введите целую часть найденной длины.
Подсказка
Путь с меньшим числом рёбер не обязательно короче: сравнивай полные суммы весов.
Решение
12: кратчайший путь 1 → 12 → 5 → 30 → 100, 3.4 + 1.9 + 2.6 + 4.7 = 12.6; прямое ребро 1 → 100 стоит 16.5.
Решение программой
from functools import cache EDGES = """1 12 3.41 5 6.112 5 1.912 30 7.25 30 2.65 100 9.830 100 4.71 100 16.5"""graph = {}for line in EDGES.splitlines(): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef f(v, t): if v == t: return 0 best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, t)) return best print(int(f(1, 100)))Ответ: 12
Вершины на цикле
Граф задан рёбрами:
3 8 1.08 5 2.05 3 1.58 9 4.09 4 0.5Сколько вершин лежит на направленном цикле?
Введите число.
Подсказка
Пройди по стрелкам из 3: удастся ли вернуться в 3?
Решение
3: цикл 3 → 8 → 5 → 3. Из 9 и 4 вернуться нельзя.
Решение программой
edges = [(3, 8), (8, 5), (5, 3), (8, 9), (9, 4)]nxt = {}for a, b in edges: nxt.setdefault(a, []).append(b) def reach(s): seen, todo = set(), [s] while todo: for u in nxt.get(todo.pop(), []): if u not in seen: seen.add(u) todo.append(u) return seen print(sum(v in reach(v) for v in {3, 8, 5, 9, 4}))Ответ: 3