Обход в ширину, когда рёбра неравные

Дек вместо очереди для весов 0 и 1, разбиение ребра для весов 1 и 2, вёдра Диала для маленьких весов — три способа не доставать Дейкстру.

6 мин

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

Веса 0 и 1: дек

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

vector<int> dist(n + 1, INF);
deque<int> dq;
dist[start] = 0;
dq.push_back(start);
while (!dq.empty()) {
    int v = dq.front();
    dq.pop_front();
    for (auto [to, w] : g[v])
        if (dist[v] + w < dist[to]) {
            dist[to] = dist[v] + w;
            if (w == 0) dq.push_front(to);
            else dq.push_back(to);
        }
}

Два отличия от обычного обхода, оба существенные.

Во-первых, условие теперь <, а не «ещё не видели»: до вершины можно добраться второй раз более дешёвым путём, и это улучшение надо принять.

Во-вторых, вершина может попасть в дек несколько раз. Значит, при снятии стоит проверять актуальность — либо флагом «уже обработана», либо сравнением сохранённого расстояния с текущим.

В деке по-прежнему лежат вершины не более чем двух соседних значений $d$ и $d+1$ , поэтому доказательство корректности почти дословно повторяет доказательство для обычного обхода. Время — $O(n + m)$ .

Замер на сетке $1000 \times 1000$ (миллион вершин, четыре миллиона рёбер, веса случайные 0 и 1): дек — 27 мс, Дейкстра на той же сетке — 101 мс. Разница в четыре раза, и она вся в логарифме кучи.

Веса 1 и 2: разбить ребро

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

if (w == 1) { g[u].push_back(v); g[v].push_back(u); }
else {
    int middle = n + i;                // своя вершина на каждое такое ребро
    g[u].push_back(middle); g[middle].push_back(u);
    g[v].push_back(middle); g[middle].push_back(v);
}

Дальше запускается обычный обход в ширину, и dist[v] сразу получается настоящим расстоянием: путь через промежуточную вершину состоит из двух единичных рёбер.

Цена — рост графа: на $m$ рёбер добавляется до $m$ вершин. При $n, m \le 10^5$ это ерунда, при $m \le 10^7$ уже нет.

Приём обобщается на любые небольшие целые веса: ребро веса $w$ разбивается на $w$ единичных, и граф вырастает в $\sum w$ . Поэтому годится он только пока веса маленькие: на весах до $10^9$ это, разумеется, невозможно.

Существенное ограничение: восстанавливать путь по такому графу надо аккуратно, потому что в нём есть вершины, которых в исходной задаче нет. Обычно расстояния считают на разбитом графе, а спуск ведут по исходным рёбрам, проверяя условие $\mathrm{dist}[to] + w = \mathrm{dist}[v]$ .

Небольшие целые веса: вёдра Диала

Если веса целые и не превосходят $C$ , а длина кратчайшего пути не превосходит $D$ , работает такой приём: завести массив списков buckets[0..D] и перебирать значения расстояния по возрастанию.

vector<vector<int>> buckets(D + 1);
buckets[0].push_back(start);
for (int d = 0; d <= D; d++)
    for (size_t i = 0; i < buckets[d].size(); i++) {   // размер растёт по ходу
        int v = buckets[d][i];
        if (dist[v] != d) continue;                    // устаревшая запись
        for (auto [to, w] : g[v])
            if (d + w < dist[to]) { dist[to] = d + w; buckets[d + w].push_back(to); }
    }

Это ровно Дейкстра, у которой куча заменена на массив вёдер. Время $O(n + m + D)$ , память — те же порядки. Обход в ширину получается частным случаем при $C = 1$ : тогда непустых вёдер ровно столько, сколько слоёв.

Обратите внимание на цикл по i вместо for (int v : buckets[d]): во время обработки ведра в него могут добавляться новые вершины — при $w = 0$ . Итератор диапазонного for этого не переживёт.

Что выбрать

веса	приём	время
все единичные	обычный обход в ширину	$O(n + m)$
0 и 1	дек	$O(n + m)$
небольшие целые, мало разных	разбиение рёбер	$O(n + \sum w)$
целые до $C$	вёдра Диала	$O(n + m + D)$
любые неотрицательные	Дейкстра	$O(m \log n)$
бывают отрицательные	Форд — Беллман	$O(nm)$

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

Где это встречается неожиданно

Вес ноль почти никогда не написан в условии прямым текстом. Он появляется, когда какое-то действие бесплатно:

пересадки в транспорте. Ехать по той же линии — бесплатно, пересесть — стоит один. Вершина здесь пара «станция и линия, по которой приехали», рёбра внутри линии весят ноль. Это уже граф состояний;
телепорты и порталы. Переход между двумя порталами бесплатен. Чтобы не проводить рёбра между всеми парами порталов — а их квадрат, — добавляют одну фиктивную вершину-концентратор и соединяют с ней все порталы рёбрами веса ноль (или веса «половина стоимости телепорта»);
бесплатная смена направления, режима, состояния — всё, где действие меняет состояние, но не стоит времени.

Первый признак, что задача про 0-1: в условии есть два разных действия, и одно из них ничего не стоит.

Смежное

Обход в ширину — база, на которой всё это стоит;
Граф состояний — как понять, что вершина не точка;
Алгоритм Дейкстры — когда веса всё-таки произвольные;
Стек, очередь и дек — устройство самой структуры.