Здравствуйте, Товарищи!!!😎😎😎 Сегодня разбираем один из фундаментальных разделов теории графов — нахождение кратчайших путей. Определение Кратчайшим путём между вершинами a и b в неориентированном графе называется путь между ними, содержащий наименьшее количество рёбер. В зависимости от контекста под длиной пути могут понимать как число рёбер k, так и число промежуточных вершин (k−1), либо общее число вершин в пути (k+1), включая начало и конец. Кратчайший путь между парой вершин не всегда уникален. Как искать кратчайшие пути Если граф не содержит циклов, задачу можно решить в духе динамического программирования. Кратчайшее расстояние до вершины v выражается через минимальное расстояние до всех возможных предыдущих вершин u: d[v] = min(d[u] + w_uv), где (u, v) — ребро графа. Чтобы посчитать эту формулу, нужно уметь для каждой вершины проходиться по всем входящим рёбрам и выбирать порядок обхода так, чтобы значения d[u] уже были вычислены. Поиск в ширину Если граф невзвешенный, то все кратчайшие пути можно найти с помощью поиска в ширину (Breadth-First Search, или просто BFS). Алгоритм можно представить как процесс «поджигания» графа: сначала «горит» стартовая вершина s, а на каждом следующем шаге огонь перекидывается на всех соседей уже горящих вершин. Номер шага, на котором вершина v загорелась, в точности равен длине кратчайшего пути от s до v. Алгоритм Дейкстры Если рёбра имеют неотрицательные веса, применяется алгоритм Дейкстры. Он находит кратчайшие пути от заданной вершины s до всех остальных. Пусть d[v] — текущее известное расстояние от s до v. Изначально d[s] = 0, а для остальных вершин расстояние считается бесконечным. На каждой итерации выбирается вершина v с минимальным d[v] среди ещё не отмеченных. После этого для всех исходящих рёбер (v, u) выполняется операция релаксации: d[u] = min(d[u], d[v] + w), где w — длина ребра (v, u). Когда все вершины обработаны, массив d содержит длины кратчайших путей. Время работы ВFS: O(n + m), где n - кол-во вершин, m - количество рёбер Дейкстра: O(n ^ 2 log n) Практика (Codeforces) Алгоритм Дейкстры? Кратчайший путь Тренировка СПбГУ Встреча Мариан и Робина Итоги Поиск в ширину юзаем для невзвешенных графов, а алгоритм Дейкстры — для графов с неотрицательными весами. Оба метода лежат в основе многих олимпиадных и прикладных задач, в основном это построение маршрутов и компьютерные сети А если хотите более подробно изучить олимпиадные темы, записывайтесь на наш курс по олимпиадному программированию, который уже стартует завтра. @postupashki_prog