wataru 25 апр в 21:17

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

Средний

5 мин

2.8K

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

Монотонность. При добавлении ребра к пути, его длина не уменьшается: $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};
};

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

Теги:

Хабы:

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

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

Применение

Публикации

Ближайшие события