В обычном графе ребро либо есть, либо нет. Но в жизни у связей есть цена: дорога длиннее или короче, канал быстрее или медленнее, кабель дороже или дешевле. Когда рёбрам приписывают числа-веса, граф становится взвешенным, и появляются две классические задачи: соединить всё дёшево и добраться быстро.

Минимальное остовное дерево

Задача: есть города, между некоторыми можно проложить кабель, у каждой линии своя стоимость. Нужно соединить все города так, чтобы суммарная стоимость была минимальной. Ответ — минимальное остовное дерево (MST, minimum spanning tree): набор рёбер, связывающий все вершины без циклов и с наименьшей суммой весов.

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

Кратчайший путь: алгоритм Дейкстры

Другая задача — не «связать всё», а «добраться из A в B быстрее всего». Например, найти кратчайший маршрут по дорогам с известной длиной. Классическое решение — алгоритм Дейкстры.

Идея такая. Для каждой вершины держим текущую лучшую известную дистанцию от старта; вначале у старта она 0, у остальных — «бесконечность». На каждом шаге берут ближайшую ещё не обработанную вершину и «расслабляют» её соседей: если через неё до соседа получается короче, чем было известно, — обновляют дистанцию соседа. Обработанную вершину больше не трогают: её кратчайшая дистанция уже окончательна. Повторяют, пока не обработают все.

Аналогия — как вода, растекающаяся от источника: она достигает каждой точки по кратчайшему пути и первой доходит до ближайших. Чтобы каждый раз быстро брать «ближайшую необработанную вершину», Дейкстра опирается на приоритетную очередь — ту же кучу. Алгоритм лежит в основе навигаторов, маршрутизации в сетях и всюду, где ищут дешёвый путь по взвешенному графу. (Важная оговорка: классический Дейкстра требует, чтобы веса рёбер были неотрицательными.)

Кроме пути между двумя точками, бывает нужен кратчайший путь между всеми парами вершин сразу — для этого есть свои алгоритмы, дающие таблицу расстояний «каждый до каждого».

Когда задача неразрешима

Взвешенные графы приводят и к задачам, которые выглядят похоже, но решаются несравнимо тяжелее. Самая знаменитая — задача коммивояжёра: найти кратчайший маршрут, проходящий через все города ровно по разу и возвращающийся в начало. Кажется, чуть сложнее кратчайшего пути — но быстрого точного алгоритма для неё не известно: число вариантов растёт факториально, и для большого числа городов перебрать их за разумное время невозможно.

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

Коротко

  • Во взвешенном графе у рёбер есть числовой вес (стоимость, длина, время), и появляются задачи оптимизации.
  • Минимальное остовное дерево (MST) связывает все вершины с наименьшей суммой весов; строится жадно — добавляем самое дешёвое ребро к уже подключённой части.
  • Алгоритм Дейкстры находит кратчайший путь от старта: обрабатывает вершины в порядке близости, обновляя дистанции соседей; опирается на приоритетную очередь и требует неотрицательных весов.
  • Некоторые задачи (коммивояжёр, гамильтоновы циклы) труднорешаемы — точного быстрого алгоритма нет; их решают приближённо. Узнавать их заранее важно, чтобы не тратить силы на безнадёжный перебор.

Дальше — как выбрать структуру данных: сводка всего раздела и практическое руководство, что брать под какую задачу.