Кратчайшие пути, DSU и остовное дерево

Перед началом: обходы графов (модуль 14), куча и container/heap (модуль 9), сортировка (модуль 8). Инструменты: Go 1.27, container/heap, sort.Slice. Трудоёмкость: ~7 ч (теория 3 ч · практика 4 ч).

🔥 Инцидент: «Маршрут из трёх перевалок дешевле, а выбрали двухперевалочный»

Планировщик доставки выбирал маршрут между складами «по числу перевалок»: когда-то это был честный BFS на графе, где все рёбра были равны — одна перевалка, один сегмент. Со временем у сегментов появились цены за палету, и равенство кончилось, а алгоритм остался: BFS просто не умеет читать веса.

После подключения дальнего хаба появился маршрут из двух перевалок против трёх, и планировщик массово перевёл потоки на него. Себестоимость выросла на 18 %: каждая перевалка в новом хабе почти втрое дороже. Хуже того, никто не заметил подмены: маршруты выглядели «короче», метрика сходилась.

Ломать нужно не данные, а алгоритм: BFS невзвешен, а нам нужен кратчайший путь по сумме весов. В этом модуле — Дейкстра и её границы, Беллман-Форд, Флойд-Уоршелл, затем DSU и MST: минимальная сеть — не минимальный маршрут.

📖 Теория

15.1 Дейкстра: жадность и куча

Дейкстра держит «лучшее известное расстояние» и жадно снимает из кучи ближайшую: её расстояние окончательно — все прочие пути к ней уже длиннее. Для каждого соседа — релаксация: «стало короче — запомни и положи в кучу».

go
h := &minHeap{{0, src}} // элементы {расстояние, вершина}
for h.Len() > 0 {
	cur := heap.Pop(h).(item)
	if cur.dist > dist[cur.node] {
		continue // устаревшая запись: вершину улучшили после push
	}
	for _, e := range adj[cur.node] {
		if nd := cur.dist + e.weight; nd < dist[e.to] {
			dist[e.to] = nd
			heap.Push(h, item{nd, e.to})
		}
	}
}

Сложность O(E log V) с кучей. Условие — неотрицательные веса: контрпример 0→1 (1), 0→2 (2), 2→1 (−2) — Дейкстра зафиксирует вершину 1 на расстоянии 1, хотя через 2 до неё 0: зафиксированное не пересматривают.

15.2 Беллман-Форд и Флойд-Уоршелл

Беллман-Форд не фиксирует ничего: V−1 раунд релаксаций всех рёбер — и расстояния сходятся даже с отрицательными весами. V-й раунд — детектор: улучшилось — достижим отрицательный цикл, конечных расстояний нет.

go
dist[src] = 0
for round := 0; round < n-1; round++ {
	for _, e := range edges {
		if d := dist[e.u] + e.w; d < dist[e.v] {
			dist[e.v] = d // релаксация: O(V·E) суммарно
		}
	}
}
// V-й раунд улучшает dist — в графе отрицательный цикл.

Флойд-Уоршелл — все пары за O(V³): разрешаем очередную k как промежуточную и улучшаем все i→j. Оправдан на малых графах (V ≤ ~500), когда нужны все пары, а веса могут быть отрицательными (без отрицательных циклов).

go
for k := range d {
	for i := range d {
		for j := range d {
			if d[i][k]+d[k][j] < d[i][j] {
				d[i][j] = d[i][k] + d[k][j]
			}
		}
	}
}

15.3 DSU: система непересекающихся множеств

DSU хранит вершины по группам и за почти O(1) отвечает: «в одной группе?» и «объединить». Оптимизации — сжатие путей и объединение по размеру.

go
// find — корень со сжатием путей: узел тянется прямо к корню.
func (d *dsu) find(x int) int {
	if d.parent[x] != x {
		d.parent[x] = d.find(d.parent[x])
	}
	return d.parent[x]
}

// union — по размеру; false означает, что a и b уже связаны.
func (d *dsu) union(a, b int) bool {
	ra, rb := d.find(a), d.find(b)
	if ra == rb {
		return false
	}
	if d.size[ra] < d.size[rb] {
		ra, rb = rb, ra
	}
	d.parent[rb], d.size[ra] = ra, d.size[ra]+d.size[rb]
	return true
}

Амортизированно — обратная функция Аккермана, практически константа. Применения: лишнее ребро, слияние аккаунтов, динамическая связность, Краскал.

15.4 MST: Краскал и Прим

Минимальное остовное дерево — подмножество из V−1 рёбер минимального суммарного веса, связывающее все вершины. Краскал: сортируем рёбра по весу и берём каждое, если оно не замыкает цикл (проверка — DSU).

go
sort.Slice(edges, func(i, j int) bool { return edges[i].w < edges[j].w })
for _, e := range edges {
	if d.union(e.u, e.v) { // ребро не создаёт цикл — берём
		cost += e.w
	}
}

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

MST и кратчайшие пути — разные задачи: на треугольнике 0—1 (1), 1—2 (1), 0—2 (1) MST берёт два ребра (сеть стоимостью 2), а кратчайший путь 0→2 — одно ребро длиной 1. MST минимизирует сеть целиком, а не маршрут в ней.

15.5 Компромиссы

Вывод: выбор диктуют знак весов, размер графа и вопрос — «один источник» или «все пары». Отрицательные веса — сразу Беллман-Форд или Флойд; соединить вершины подешевле — MST, а не кратчайший путь.

💻 Практика

1. Network delay time. Даны times [][3]int — {u, v, w}, сигнал u→v за w, число вершин n и источник k. Верните время, за которое сигнал дойдёт до всех вершин, или −1: func networkDelay(n int, times [][3]int, k int) int. Дейкстра с container/heap. Тесты: классический пример → 2; недостижимая вершина → −1; одна вершина → 0; параллельные рёбра — берётся минимальное.
2. Отрицательный цикл (Беллман-Форд). Реализуйте hasNegativeCycle(n int, edges []edge, src int) bool — отрицательный цикл, достижимый из src. Тесты: цикл из источника; цикл в недостижимой части графа → false; цикла нет; улучшение только на V-м раунде.
3. Лишнее ребро (DSU). Рёбра добавляются по одному к связному дереву на n вершинах; ровно одно ребро лишнее. Верните его: func findRedundant(edges [][2]int) [2]int. Тесты: цепочка с замыканием; звезда; лишнее ребро появляется в середине списка — какое вернёт ваш код и что требует задача.
4. Стоимость MST. func mstCost(n int, edges []edge) int — Краскал, сумма рёбер MST или −1 для несвязного графа. Затем реализуйте Прим и сравните счётчики: сколько раз вызван find у Краскала и сколько push у Прима на разреженном и на плотном графе. Тесты: одна вершина → 0; две вершины; треугольник; квадрат с диагональю; несвязный → −1.

🧩 Quiz

✅ Итоги модуля

• Дейкстра с кучей — O(E log V), но только при неотрицательных весах.
• Отрицательные веса — Беллман-Форд; все пары — Флойд-Уоршелл на малых графах.
• DSU — почти O(1): сжатие путей плюс объединение по размеру.
• Краскал и Прим строят один и тот же MST: выбор — по плотности графа.
• MST минимизирует сеть целиком, кратчайший путь — конкретный маршрут.

🔗 Мостик к Модулю 16

Графы и структуры позади. Дальше — техника, которая собирает решения из подзадач: динамическое программирование. Модуль 16: мемоизация → таблица, 1D DP и rolling array — от лестницы и «ограбить дома» до размена монет, с измерением, сколько памяти экономит переиспользование строки таблицы.