Обобщенный алгоритм Дейкстры / Habr

Алгоритм Дейкстры можно обобщить на произвольную функцию длины пути, если только она удовлетворяет трем условиям:

Монотонность. При добавлении ребра к пути, его длина не уменьшается: $Len(path+e) \ge Len(path)$
Консистентность. При добавлении одинакового ребра к путям одинаковой длины, получившиеся новые пути имеют одинаковую длину: $Len(path_1) = Len(path_2) \Rightarrow Len(path_1 + e) = Len(path_2+e)$
Оптимальность начала. Если к двум путям приписать одинаковое ребро, то кратчайший путь останется кратчайшим: $Len(path_1) \le Len(path_2) \Rightarrow Len(path_1+e) \le Len(path_2+e)$

Этим условиям удовлетворяет обычная аддитивная функция длины пути (сумма длин всех ребер в пути), покуда ребра неотрицательные. Им же удовлетворяет функция "максимальная вершина в пути". Это позволяет решать через Дейкстру, например, вот эту задачу на литкоде: Trapping rain water II. Еще, этим свойствам удовлетворяет аддитивная длина пути с потенциалами, использующаяся в алгоритме Джонсона для поиска кратчайших путей в графе с отрицательными ребрами (но без отрицательных циклов).

Вот обобщенный алгоритм Дейкстры:

 1 function Dijkstra(Graph, source):
 2      
 3       for each vertex v in Graph.Vertices:
 4           dist[v] ← INFINITY
 5           prev[v] ← UNDEFINED
 6           add v to Q
 7       dist[source] ← Length({}) # длина пустого пути без ребер.
 8       
 9       while Q is not empty:
10           u ← vertex in Q with minimum dist[u]
11           if dist[u] = INFIINTY: break
12           remove u from Q
13            
14           for each neighbor v of u still in Q:
15               alt ← Length(dist[u], Graph.Edges(u, v))
16               if alt < dist[v]:
17                   dist[v] ← alt
18                   prev[v] ← u
19   
20       return dist[], prev[]

Вся разница со стандартным алгоритмом в том, что в строке 15, вместо сложения расстояния до u и длины ребра u->v мы вызываем какую-то функцию длины. Ну и в строке 7 инициализируем расстояние до старта чем-то, возможно отличающимся от 0. Например, если у нас длина пути - произведение всех ребер в пути, то пустой путь должен иметь длину 1.

Доказательство корректности

Поддерживается инвариант, что до вершин из множества W=V/Q найдены кратчайшие расстояния, а для всех вершин в Q подсчитаны кратчайшие пути, в которых все ребра, кроме последнего, идут между вершинами в W. Назавем такие пути "торчащими из W".

Инвариант верен в самом начале. W пустое и для всех вершин dist - бесконечно, ибо путей, как описано выше в графе нет. В dist[source] подсчитан единственный торчащий из {} путь в графе - пустой путь.

Далее, обозначим за u вершину из Q для которой dist[] минимально. Утверждается, что для нее dist[] совпадает с кратчайшим путем в графе. Рассмотрим все пути из source в u. Поскольку source лежит в W, а u в Q, то любой такой путь сначала сколькими-то ребрами лежит в W, а потом идет реберо из W в Q. Т.е. он начинается с какого-то "торчащего из W" пути. Допустим это ребро идет в вершину v (которая может совпадать или не совпадать с u). Длина части пути до v не меньше dist[u], потому что dist[u] - это минимум из всех торчащих из W путей. Но рассматриваемый путь может продолжаться и после вершины v. По свойству монотонности длина пути может только увеличится. В итоге этот произвольный путь в u имеет длину не меньше dist[u], потому что у него начало как минимум длины dist[u]. Раз все пути не короче dist[u], то dist[u] - это кратчайшее расстояние до u. По построению это длина какого-то пути, Поэтому u можно перенести из Q в W.

Далее, для поддержания инварианта надо пересчитать dist[]. Множество торчащих путей из W которые мы учитываем в dist изменилось, туда добавились пути выходящие из u. Надо их все рассмотреть и учесть. По свойству оптимальности префикса, если мы хотим получить кратчайший путь, проходящий через u, то мы должны взять кратчайший путь в u и приписать к нему одно ребро. По свойству консистентности мы можем посчитать длину пути через u в v через длину начала dist[u] и ребро u->v.

В итоге, после внутреннего цикла по ребрам инвариант вновь выполняется.

Алгоритм завершается, потому что на каждом шаге конечное множество Q уменьшается на один элемент.

В самом конце инваринат выполняется, а значит для всех достижимых вершин будет подсчитано кратчайшее расстояние. Для не достижимых вершин будет корректно подсчитана бесконечная длина. ЧТД

Это доказательство не требует какой-то конкретной функции длины пути и лишь опирается на 3 указаных в начале свойства.

Применение

Примеры удовлетворяющих условиям функций длины:

Max(w_i) - максимальное ребро в пути. Например, у вас плохая машина и ей тяжело ехать быстро. Но в потоке машин вам будет безопаснее ехать с максимально разрешенной скоростью вместе со всеми. Поэтому вам надо найти маршрут на котором максимальное ограничение скорости как можно меньше.
p_start + Sum(w_i) - p_end - длина пути с потенциалами. Используется в алгоритме Джонсона и основанном на нем алгоритме поиска максимального потока минимальной стоимости.
Произведение длин ребер. Все длины >= 1.
Комбинация суммы и максимума: Вам надо найти путь минимальной (обычной) длины, и среди всех таких тот, где максимальная цена ребра минимальна.
Сумма чисел в посещенных вершинах.
Максимум из чисел в посещенных вершинах.

Если хоть одно условие нарушено, то алгоритм дейкстры тут не применим. Можно подобрать граф, в котором алгоритм выдаст неправильный ответ. Примеры не удовлетворяющих условиям функций длины:

Комбинация максимума и суммы: Нужно найти путь с минимальной максимальной стоимостью ребра в пути, среди всех таких с минимальной длиной (обычная сумма).
Длина пути зависит от истории. Например, вершины - это перекрестки, а ребра - дороги между ними. Длина ребра зависит от того, с какой стороны вы попали в перекресток (например, при проезде прямо вам не надо тормозить и разгонятся).
Сумма длин ребер, но длины могут быть отрицательными.
Наименьшее общее кратное всех длин ребер.

Ну и напоследок, решение задачи Trapping rain water II:
будем считать высоту столбика воды в каждой конкретной клетке. Какой высоты она может быть (смотрим тут на абсолютную высоту над "уровнем моря")? Вода не стекает за гра��ицу карты. Но вода может стекать по любому пути из клетки за границу (если ходить по 4 направлениям). Рассмотрим путь, какой высоты столбик должен быть, чтобы не стекать вдоль этого пути? Максимальная высота вдоль пути! Максимальный столбик в пути не даст воде стекать ниже его уровня. Если же вода будет стоять выше, то она без препятствий утечет. Это работает, даже если начальный столбик - максимальный. Просто считаем что там какой-то епсилон воды на поверхности прилип и никуда не стекает. Итак, в клетке высота будет - минимум по всем возможным путям от максимума всех клеток вдоль пути. Это в точности расстояние от клетки до границы карты, где функция длины пути - максимальное число в вершине. Поскольку нам надо найти путь от каждой клетки до границы карты, можно делать наоборот - ввести вершину "сток", которая соеденина со всеми граничными клетками и искать расстояния из нее до всех клеток на карте.

Вот код:

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int n = heightMap.size();
        int m = heightMap[0].size();

        // Очередь с приоритетом для Дейкстры.
        set<array<int,3>> queue;
        // Найденные расстояния.
        vector<vector<int>> dist(n, vector<int>(m, -1));

        // Сначала отдельно обработаем вершину "сток" за границей карты.
        // Расстояние до нее будет 0 и надо релаксировать из нее ребра
        // во все клетки на границе карты.
        for (int i = 0; i < n; ++i) {
            queue.insert({heightMap[i][0], i, 0});
            dist[i][0] = heightMap[i][0];
            queue.insert({heightMap[i][m-1], i, m-1});
            dist[i][m-1] = heightMap[i][m-1];
        }
        for (int j = 0; j < m; ++j) {
            queue.insert({heightMap[0][j], 0, j});
            dist[0][j] = heightMap[0][j];
            queue.insert({heightMap[n-1][j], n-1, j});
            dist[n-1][j] = heightMap[n-1][j];
        }

        // Сразу будем считать ответ.
        int total_volume = 0;

        while (!queue.empty()) {
            // Вершина с минимальной оценкой.
            auto cur = *queue.begin();           
            queue.erase(queue.begin());

            int cur_dist = cur[0];
            int x = cur[1];
            int y = cur[2];
          
            // Объем воды - надо из высоты столба воды вычесть высоту дна.
            total_volume += cur_dist - heightMap[x][y];

            // Релаксируем ребра из данной вершины.
            // Перебираем 4 соседа.
            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                // Вот она, функция расстояния! 
                // Максимум из значений в посещенных вершинах.
                int new_dist = max(cur_dist, heightMap[nx][ny]);
                // Обновляем значение в очереди с приоритетом
                if (dist[nx][ny] == -1) {
                    // Если оценки для вершины раньше не было
                    // просто помещаем в очередь.
                    dist[nx][ny] = new_dist;
                    queue.insert({new_dist, nx, ny});
                } else if (dist[nx][ny] > new_dist) {
                    // Иначе, не забываем удалить оттуда старое
                    // значение.
                    queue.erase({dist[nx][ny], nx, ny});
                    dist[x][y] = new_dist;
                    queue.insert({new_dist, nx, ny});
                }
            }
        }

        return total_volume;
    }

    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};
};

Если вам известны другие задачи, в которых можно этот алгоритм применить, буду благодарен, если сообщите о них в комментариях.