算法【Dijkstra算法及分层图最短路】

Dijkstra算法：给定一个源点，求解从源点到每个点的最短路径长度。单源最短路径算法。

适用范围：有向图、边的权值没有负数。

彻底暴力的Dijkstra算法，不讲、时间复杂度太差、无意义。

普通堆实现的Dijkstra算法，最普遍、最常用。

算法核心过程：

节点弹出过就忽略，节点没弹出过，让其它没弹出节点距离变小的记录加入堆。

反向索引堆实现的Dijkstra算法，最快速、最极致。

普通堆实现的Dijkstra算法，时间复杂度O(m * log m)，m为边数。

1.distance[i]表示从源点到i点的最短距离，visited[i]表示i节点是否从小根堆弹出过。

2.准备好小根堆，小根堆存放记录：(x点，源点到x的距离)，小根堆根据距离组织。

3.令distance[源点]=0，(源点，0)进入小根堆。

4.从小根堆弹出(u点，源点到u的距离)

   a. 如果visited[u] == true，不做任何处理，重复步骤4。

   b. 如果visited[u] == false，令visited[u] = true，u就算弹出过了

      然后考察u的每一条边，假设某边去往v，边权为w。

      1）如果visited[v] == false 并且 distance[u] + w < distance[v]

         令distance[v] = distance[u] + w，把(v, distance[u] + w)加入小根堆。

      2）处理完u的每一条边之后，重复步骤4。

5.小根堆为空过程结束，distance表记录了源点到每个节点的最短距离。

反向索引堆实现的Dijkstra算法，时间复杂度O(m * log n)，n为节点数，m为边数。

1.准备好反向索引堆，根据源点到当前点的距离组织小根堆，可以做到如下操作

   a. 新增记录(x, 源点到x的距离)   b. 当源点到x的距离更新时，可以进行堆的调整

   c. x点一旦弹出，以后忽略x       d. 弹出堆顶的记录(u, 源点到u的距离)

2.把(源点，0)加入反向索引堆，过程开始。

3.反向索引堆弹出(u，源点到u的距离)，考察u的每一条边，假设某边去往v，边权为w

   1）如果v没有进入过反向索引堆里，新增记录(v, 源点到u的距离 + w)。

   2）如果v曾经从反向索引堆弹出过，忽略。

   3）如果v在反向索引堆里，看看源点到v的距离能不能变得更小，如果能，调整堆；不能，忽略。

   4）处理完u的每一条边，重复步骤3。

4.反向索引堆为空过程结束。反向索引堆里记录了源点到每个节点的最短距离。

分层图最短路，又叫扩点最短路。

不把实际位置看做图上的点，而是把 实际位置及其状态的组合看做是图上的点，然后搜索bfs或者Dijkstra的过程不变，只是扩了点（分层）而已。原理简单，核心在于如何扩点、如何到达、如何算距离，每个题可能都不一样。

下面通过几个题目加深理解。

题目一

测试链接：https://leetcode.cn/problems/network-delay-time

分析：这个题就是一个Dijkstra算法模板。找到最晚时间就是结果。下面分别给出使用堆，也就是优先队列的做法以及使用反向索引堆的做法。代码如下。

class Solution {
public:
    int Head[101] = {0};
    int Next[6001] = {0};
    int To[6001] = {0};
    int Weigth[6001] = {0};
    int cnt = 1;
    int distance[101];
    bool poped[101] = {false};
    void build(vector<vector<int>>& times, int n){
        int length = times.size();
        for(int i = 0;i < length;++i){
            Next[cnt] = Head[times[i][0]];
            Head[times[i][0]] = cnt;
            To[cnt] = times[i][1];
            Weigth[cnt] = times[i][2];
            ++cnt;
        }
        for(int i = 1;i <= n;++i){
            distance[i] = -((1 << 31) + 1);
        }
    }
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        build(times, n);
        int ans = 0;
        int num = n;
        auto cmp = [](vector<int> v1, vector<int> v2)->bool{
            return v1[1] > v2[1];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
        vector<int> temp;
        temp.push_back(k);
        temp.push_back(0);
        distance[k] = 0;
        --num;
        q.push(temp);
        temp.clear();
        while (!q.empty())
        {
            temp = q.top();
            q.pop();
            if(poped[temp[0]] == true){
                continue;
            }
            poped[temp[0]] = true;
            ans = ans > distance[temp[0]] ? ans : distance[temp[0]];
            for(int next = Head[temp[0]];next != 0;next = Next[next]){
                if(Weigth[next] + temp[1] < distance[To[next]]){
                    if(distance[To[next]] == -((1 << 31) + 1)){
                        --num;
                    }
                    vector<int> tmp;
                    tmp.push_back(To[next]);
                    tmp.push_back(Weigth[next] + temp[1]);
                    q.push(tmp);
                    distance[To[next]] = Weigth[next] + temp[1];
                }
            }
        }
        return num == 0 ? ans : -1;
    }
};

其中，采用链式前向星建图；具体过程和上面写的Dijkstra算法流程一样。下面是采用反向索引堆的做法。代码如下。

class Solution {
public:
    int Head[101] = {0};
    int Next[6001] = {0};
    int To[6001] = {0};
    int Weight[6001] = {0};
    int cnt = 1;
    int heap[101];
    int where[101];
    int distance[101];
    int heapSize = 0;
    void Build(vector<vector<int>>& times, int n){
        int length = times.size();
        for(int i = 0;i < length;++i){
            Next[cnt] = Head[times[i][0]];
            Head[times[i][0]] = cnt;
            To[cnt] = times[i][1];
            Weight[cnt] = times[i][2];
            ++cnt;
        }
        for(int i = 1;i <= n;++i){
            distance[i] = -((1 << 31) + 1);
            where[i] = -1;
        }
    }
    void heapInsert(int i){
        int father = (i-1) / 2;
        while (distance[heap[i]] < distance[heap[father]])
        {
            swap(i, father);
            i = father;
            father = (i-1) / 2;
        }
    }
    void heapify(int i){
        int l = 2 * i + 1;
        while (l < heapSize)
        {
            int best = l+1 < heapSize && distance[heap[l]] > distance[heap[l+1]] ? l+1 : l;
            best = distance[heap[i]] < distance[heap[best]] ? i : best;
            if(best == i){
                break;
            }
            swap(i, best);
            i = best;
            l = 2 * i + 1;
        }
    }
    void swap(int a, int b){
        int temp = heap[a];
        heap[a] = heap[b];
        heap[b] = temp;
        where[heap[a]] = a;
        where[heap[b]] = b;
    }
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        int num = n;
        int ans = 0;
        Build(times, n);
        distance[k] = 0;
        --num;
        heap[0] = k;
        where[k] = 0;
        ++heapSize;
        while (heapSize != 0)
        {
            int cur = heap[0];
            int cur_distance = distance[cur];
            swap(0, heapSize-1);
            where[cur] = -2;
            ans = ans > cur_distance ? ans : cur_distance;
            --heapSize;
            heapify(0);
            for(int next = Head[cur];next != 0;next = Next[next]){
                int to = To[next];
                int weight = Weight[next];
                if(where[to] == -1){
                    heap[heapSize] = to;
                    distance[to] = cur_distance + weight;
                    --num;
                    where[to] = heapSize;
                    ++heapSize;
                    heapInsert(heapSize-1);
                }else if(where[to] == -2){
                    continue;
                }else{
                    if(cur_distance + weight < distance[to]){
                        distance[to] = cur_distance + weight;
                        heapInsert(where[to]);
                    }
                }
            }
        }
        return num == 0 ? ans : -1;
    }
};

其中，采用链式前向星建图；并且堆使用自己定义的堆，heapInsert方法代表从i位置向上调整堆，heapify方法代表从i位置向下调整堆。

题目二

测试链接：https://leetcode.cn/problems/path-with-minimum-effort/

分析：这也是一个Dijkstra算法模板和第一题主体代码类似，只不过给出的数据就相当于图，就没在建图。代码如下。

class Solution {
public:
    int arr[5] = {0, 1, 0, -1, 0};
    int distance[100][100];
    bool poped[100][100];
    void build(int row, int column){
        for(int i = 0;i < row;++i){
            for(int j = 0;j < column;++j){
                distance[i][j] = -((1 << 31) + 1);
                poped[i][j] = false;
            }
        }
    }
    int minimumEffortPath(vector<vector<int>>& heights) {
        int row = heights.size();
        int column = heights[0].size();
        build(row, column);
        auto cmp = [](vector<int> v1, vector<int> v2){
            return v1[2] > v2[2];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
        vector<int> temp;
        temp.push_back(0);
        temp.push_back(0);
        temp.push_back(0);
        distance[0][0] = 0;
        q.push(temp);
        temp.clear();
        while (!q.empty())
        {
            temp = q.top();
            q.pop();
            if(poped[temp[0]][temp[1]] == true){
                continue;
            }
            poped[temp[0]][temp[1]] = true;
            for(int index = 0;index < 4;++index){
                if(temp[0]+arr[index] >= 0 && temp[0]+arr[index] < row
                && temp[1]+arr[index+1] >= 0 && temp[1]+arr[index+1] < column){
                    int cost = temp[2] > abs(heights[temp[0]][temp[1]] - heights[temp[0]+arr[index]][temp[1]+arr[index+1]]) ?
                    temp[2] : abs(heights[temp[0]][temp[1]] - heights[temp[0]+arr[index]][temp[1]+arr[index+1]]);
                    if(cost < distance[temp[0]+arr[index]][temp[1]+arr[index+1]]){
                        vector<int> tmp;
                        tmp.push_back(temp[0]+arr[index]);
                        tmp.push_back(temp[1]+arr[index+1]);
                        tmp.push_back(cost);
                        distance[temp[0]+arr[index]][temp[1]+arr[index+1]] = cost;
                        q.push(tmp);
                    }
                }
            }
        }
        return distance[row-1][column-1];
    }
};

其中，由于图的特殊性，邻接节点为上下左右的点，所以代码也像分支限界法。

题目三

测试链接：https://leetcode.cn/problems/swim-in-rising-water/

分析：这道题和题目二思路大致一样，只不过需要判断的东西不同。代码如下。

class Solution {
public:
    int arr[5] = {0, -1, 0, 1, 0};
    int distance[50][50];
    bool poped[50][50] = {false};
    void build(int n){
        for(int i = 0;i < n;++i){
            for(int j = 0;j < n;++j){
                distance[i][j] = -((1 << 31) + 1);
            }
        }
    }
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        build(n);
        auto cmp = [](vector<int> v1, vector<int> v2){
            return v1[2] > v2[2];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
        distance[0][0] = 0;
        vector<int> temp;
        temp.push_back(0);
        temp.push_back(0);
        temp.push_back(grid[0][0]);
        q.push(temp);
        temp.clear();
        while (!q.empty())
        {
            temp = q.top();
            q.pop();
            if(temp[0] == n-1 && temp[1] == n-1){
                return temp[2];
            }
            if(poped[temp[0]][temp[1]] == true){
                continue;
            }
            poped[temp[0]][temp[1]] = true;
            for(int index = 0;index < 4;++index){
                if(temp[0]+arr[index] >= 0 && temp[0]+arr[index] < n
                && temp[1]+arr[index+1] >= 0 && temp[1]+arr[index+1] < n){
                    int cost = temp[2] > grid[temp[0]+arr[index]][temp[1]+arr[index+1]] ?
                    temp[2] : grid[temp[0]+arr[index]][temp[1]+arr[index+1]];
                    if(cost < distance[temp[0]+arr[index]][temp[1]+arr[index+1]]){
                        distance[temp[0]+arr[index]][temp[1]+arr[index+1]] = cost;
                        vector<int> tmp;
                        tmp.push_back(temp[0]+arr[index]);
                        tmp.push_back(temp[1]+arr[index+1]);
                        tmp.push_back(cost);
                        q.push(tmp);
                    }
                }
            }
        }
        return 0;
    }
};

其中，也是因为这个图中节点的邻接节点就是四周的节点，所以感觉起来也像是分支限界法。

题目四

测试链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys

分析：这道题就是分层图最短路的一个题，图中的节点并不是单纯的位置，而是一个位置加上这个处于这个位置的钥匙状态，组成了一个节点。就可以看成一个位置，因为处在这个位置的具有钥匙状态的不一样，从而一个位置可以分层，从而这个图就变成了分层图。而因为图的特殊性，邻接节点就是四周的点，所以对于分层图，我们可以使用bfs展开。一旦得到钥匙状态为具有全部钥匙则返回移动次数，即可得到最小移动次数。代码如下。

class Solution
{
public:
    int k = 0;
    bool visited[30][30][64] = {false};
    int arr[5] = {0, 1, 0, -1, 0};
    void get_k(vector<string> &grid, int row, int column, int &begin_x, int &begin_y)
    {
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < column; ++j)
            {
                if ('a' <= grid[i][j] && grid[i][j] <= 'f')
                {
                    ++k;
                }
                if (grid[i][j] == '@')
                {
                    begin_x = i;
                    begin_y = j;
                }
            }
        }
    }
    int shortestPathAllKeys(vector<string> &grid)
    {
        int row = grid.size();
        int column = grid[0].size();
        int begin_x, begin_y;
        int step = 0;
        int cur_x, cur_y, cur_key, next_x, next_y, next_key, bit, nums;
        get_k(grid, row, column, begin_x, begin_y);
        queue<vector<int>> q;
        vector<int> first;
        first.push_back(begin_x);
        first.push_back(begin_y);
        first.push_back(0);
        q.push(first);
        visited[begin_x][begin_y][0] = true;
        while (!q.empty())
        {
            nums = q.size();
            for (int i = 0; i < nums; ++i)
            {
                cur_x = q.front()[0];
                cur_y = q.front()[1];
                cur_key = q.front()[2];
                q.pop();
                if (cur_key == (int)(pow(2, k) - 1))
                {
                    return step;
                }
                for (int index = 0; index < 4; ++index)
                {
                    next_x = cur_x + arr[index];
                    next_y = cur_y + arr[index + 1];
                    if (next_x >= 0 && next_x < row && next_y >= 0 && next_y < column && grid[next_x][next_y] != '#')
                    {
                        if (grid[next_x][next_y] == '.' || grid[next_x][next_y] == '@')
                        {
                            if (!visited[next_x][next_y][cur_key])
                            {
                                visited[next_x][next_y][cur_key] = true;
                                vector<int> temp;
                                temp.push_back(next_x);
                                temp.push_back(next_y);
                                temp.push_back(cur_key);
                                q.push(temp);
                            }
                        }
                        else if (grid[next_x][next_y] >= 'a' && grid[next_x][next_y] <= 'f')
                        {
                            bit = grid[next_x][next_y] - 'a';
                            next_key = (cur_key | (1 << bit));
                            if (!visited[next_x][next_y][next_key])
                            {
                                visited[next_x][next_y][next_key] = true;
                                vector<int> temp;
                                temp.push_back(next_x);
                                temp.push_back(next_y);
                                temp.push_back(next_key);
                                q.push(temp);
                            }
                        }
                        else if (grid[next_x][next_y] >= 'A' && grid[next_x][next_y] <= 'F')
                        {
                            bit = grid[next_x][next_y] - 'A';
                            if ((cur_key & (1 << bit)) && !visited[next_x][next_y][cur_key])
                            {
                                visited[next_x][next_y][cur_key] = true;
                                vector<int> temp;
                                temp.push_back(next_x);
                                temp.push_back(next_y);
                                temp.push_back(cur_key);
                                q.push(temp);
                            }
                        }
                    }
                }
            }
            ++step;
        }
        return -1;
    }
};

其中，对于钥匙状态采用位图的方式存储，即有a钥匙，则第0位为1，有b钥匙则第1位为1，关于位图的具体操作，可以查看之前的文章。

题目五

测试链接：https://leetcode.cn/problems/DFPeFJ/

分析：这个也是一个分层图最短路，图中节点并不是单纯的城市，而是这个城市以及处于这个城市所具有的电量。并且这个题需要我们自己建图，不像上一题有图的特殊性，所以我们采用Dijkstra流程展开。代码如下。

class Solution {
public:
    int Head[101] = {0};
    int Next[401] = {0};
    int To[401] = {0};
    int Weight[401] = {0};
    int count = 1;
    bool poped[100][101] = {false};
    void build(vector<vector<int>>& paths){
        int length = paths.size();
        for(int i = 0;i < length;++i){
            Next[count] = Head[paths[i][0]+1];
            Head[paths[i][0]+1] = count;
            To[count] = paths[i][1]+1;
            Weight[count] = paths[i][2];
            ++count;
            Next[count] = Head[paths[i][1]+1];
            Head[paths[i][1]+1] = count;
            To[count] = paths[i][0]+1;
            Weight[count] = paths[i][2];
            ++count;
        }
    }
    int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {
        cout<<end<<endl;
        build(paths);
        auto cmp = [](vector<int> v1, vector<int> v2)->bool{
            return v1[2] > v2[2];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
        vector<int> first;
        int cur_city, cur_oil, cur_time, next_city, next_oil, next_time, to_city, to_oil;
        first.push_back(start);
        first.push_back(0);
        first.push_back(0);
        q.push(first);
        while (!q.empty())
        {
            cur_city = q.top()[0];
            cur_oil = q.top()[1];
            cur_time = q.top()[2];
            q.pop();
            if(cur_city == end){
                return cur_time;
            }
            if(poped[cur_city][cur_oil] == true){
                continue;
            }
            poped[cur_city][cur_oil] = true;
            if(cur_oil < cnt){
                if(poped[cur_city][cur_oil+1] == false){
                    next_city = cur_city;
                    next_oil = cur_oil + 1;
                    next_time = cur_time + charge[cur_city];
                    vector<int> temp;
                    temp.push_back(next_city);
                    temp.push_back(next_oil);
                    temp.push_back(next_time);
                    q.push(temp);
                }
            }
            for(int next = Head[cur_city+1];next != 0;next = Next[next]){
                to_city = To[next]-1;
                to_oil = Weight[next];
                if(to_oil <= cur_oil && poped[to_city][cur_oil-to_oil] == false){
                    next_oil = cur_oil - to_oil;
                    next_city = to_city;
                    next_time = cur_time + to_oil;
                    vector<int> temp;
                    temp.push_back(next_city);
                    temp.push_back(next_oil);
                    temp.push_back(next_time);
                    q.push(temp);
                }
            }
        }
        return 0;
    }
};

其中，采用链式前向星建图；对于一个节点，如果电量不满则可以选择在当前城市充电以及满足条件的话可以去到另一城市，直到第一次到达目标城市即可得到答案。

题目六

测试链接：https://www.luogu.com.cn/problem/P4568

分析：这道题和上一题比较类似，节点为一个城市以及处于这个城市还具有多少次免费搭乘飞机的次数。但是这里在扩展节点的时候，有一点小贪心。我们不能随便使用这个免费次数，只有当到达下一个城市且下一个城市的免费次数为当前免费次数减1的费用大于处于当前城市且处于当前免费次数时，我们才会使用这个免费次数。如果不使用免费次数，则代表着到达下一个城市且免费次数和当前免费次数相同的状态的费用大于处于当前城市且当前免费次数的费用加上去往下一城市的费用。分别对应代码中for循环第一个if和第二个if。代码如下。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, k;
int s, t;
int Head[10001] = {0};
int Next[100001] = {0};
int To[100001] = {0};
int Weight[100001] = {0};
int cnt = 1;
int Distance[10001][11];
bool poped[10001][11] = {false};
int get_ans(int begin, int end, int k){
    int cur_city, cur_k, cur_cost, next_city, to_cost;
    auto cmp = [](vector<int> v1, vector<int> v2)->bool{
        return v1[2] > v2[2];
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
    vector<int> frist;
    frist.push_back(begin);
    frist.push_back(k);
    frist.push_back(0);
    Distance[begin][k] = 0;
    q.push(frist);
    while (!q.empty())
    {
        cur_city = q.top()[0];
        cur_k = q.top()[1];
        cur_cost = q.top()[2];
        q.pop();
        if(cur_city == end){
            return cur_cost;
        }
        if(poped[cur_city][cur_k] == true){
            continue;
        }
        poped[cur_city][cur_k] = true;
        for(int next = Head[cur_city+1];next != 0;next = Next[next]){
            next_city = To[next]-1;
            to_cost = Weight[next];
            if(cur_k > 0 && Distance[next_city][cur_k-1] > Distance[cur_city][cur_k]){
                Distance[next_city][cur_k-1] = Distance[cur_city][cur_k];
                vector<int> temp;
                temp.push_back(next_city);
                temp.push_back(cur_k-1);
                temp.push_back(Distance[cur_city][cur_k]);
                q.push(temp);
            }
            if(Distance[next_city][cur_k] > Distance[cur_city][cur_k] + to_cost){
                Distance[next_city][cur_k] = Distance[cur_city][cur_k] + to_cost;
                vector<int> temp;
                temp.push_back(next_city);
                temp.push_back(cur_k);
                temp.push_back(Distance[cur_city][cur_k] + to_cost);
                q.push(temp);
            }
        }
    }
    return 0;
}
void build(){
    for(int i = 0;i < 10001;++i){
        for(int j = 0;j <= 10;++j){
            Distance[i][j] = -((1 << 31) + 1);
        }
    }
}
int main(void){
    int a, b, c;
    scanf("%d%d%d", &n, &m, &k);
    scanf("%d%d", &s, &t);
    for(int i = 0;i < m;++i){
        scanf("%d%d%d", &a, &b, &c);
        Next[cnt] = Head[a+1];
        Head[a+1] = cnt;
        To[cnt] = b+1;
        Weight[cnt] = c;
        ++cnt;
        Next[cnt] = Head[b+1];
        Head[b+1] = cnt;
        To[cnt] = a+1;
        Weight[cnt] = c;
        ++cnt;
    }
    build();
    printf("%d", get_ans(s, t, k));
}

其中，采用链式前向星建图；主体流程和之前分层图最短路一样，只是for循环中需要注意一下。