Skip to content

Dijkstra

Dijkstra算法是一种局部贪心策略，用于解决带权有向图的单源最短路，其基本要求是权值中不存在负数。

实现

朴素dijkstra依赖邻接矩阵实现，通过dist和pre数组分别记录点到源点的最短距离、每个点的前驱节点。
由于邻接表在稀疏图存储空间上表现不佳，也为了优化查点效率，可以使用小根堆存储当前距离源点最近点。c++中，通常使用有自定义比较的优先队列来实现。

总体步骤如下：

  1. 初始化。

    初始化dist数组为极大值INF，表示源点到节点i的最小距离；
    初始化pre数组为-1，值表示在最短路中节点i的前一个节点；
    向优先队列中压入起点，通常是节点1。

  2. 遍历

    • 查优先队列中的最近点并弹出，如果已访问或总距离比dist中记录的最小距离小，跳过，否则标记访问；
    • 检查当前最近点能直接到达的所有点，更新dist和pre数组

  3. 输出结果

模板题

朴素最短路

题目链接：47. 参加科学大会（第六期模拟笔试）

点击展开题目
# 题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

# 输入描述

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

# 输出描述

输出一个整数，代表小明从起点到终点所花费的最小时间。

# 输入示例
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9
# 输出示例
1
12
# 提示信息

能够到达的情况：

如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。

img

不能到达的情况：

如下图所示，当从起始车站不能到达终点车站时，则输出 -1。

img

数据范围：

1 <= N <= 500;
1 <= M <= 5000;

实现代码
点击展开代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct compare{
    bool operator()(pair<int,int> a,pair<int,int> b){
        return a.second>b.second;
    }
};

const int INF=0x3f3f3f3f;
const int MAX=505;
int n,m,a,b,w;
int dist[MAX];
bool flag[MAX];
int pre[MAX];       //前驱节点
vector<pair<int,int>> map[MAX];     //指向节点，花费
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;   //指向节点，花费

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>w;
        map[a].push_back({b,w});
    }

    //初始化
    for(int i=1;i<=n;i++){
        pre[i]=-1;
        dist[i]=INF;
    }

    dist[1]=0;
    pq.push({1,0});

    //dijkstra
    int minCost=INF,minPoint=-1;
    while(!pq.empty()){
        //查最近点
        pair<int,int> currPoint=pq.top();
        pq.pop();
        minCost=currPoint.second;
        minPoint=currPoint.first;

        if(dist[minPoint]<minCost)continue;
        if(flag[minPoint])continue;
        flag[minPoint]=true;

        //更新最近点可达点和源点的距离
        for(auto point:map[minPoint]){
            if(!flag[point.first]&&minCost+point.second<dist[point.first]){
                pq.push({point.first,minCost+point.second});
                dist[point.first]=minCost+point.second;
                pre[point.first]=minPoint;
            }
        }
    } 

    if(dist[n]==INF)cout<<-1;
    else cout<<dist[n];

    return 0;
}

小根堆

题目链接：743. 网络延迟时间 - 力扣（LeetCode）

思路

和上一个模板不同，该题要求访问所有点，并找出其中最大的值。
为了访问所有节点，可以在初始化后将所有节点都放进优先队列，直到清空队列才退出处理。

实现代码
点击展开代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <queue>
#include <vector>

class Solution {
public:
    const int MAX = 105;
    const int INF = 2147483647;
    vector<pair<int, int>> graph[105]; // target,dist
    int dist[105], pre[105];
    bool flag[105];

    struct compare {
        bool operator()(pair<int, int> a, pair<int, int> b) {
            return a.second > b.second;
        }
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare>
        pq; // target,dist

    // 表，点数，起点
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 建图
        for (auto t : times) {
            graph[t[0]].push_back({t[1], t[2]});
        }

        // 初始化
        for (int i = 1; i <= n; i++) {
            dist[i] = INF;
            pre[i] = -1;
        }
        dist[k] = 0;
        for (auto point : graph[k])
            dist[point.first] = point.second;
        for (int i = 1; i <= n; i++)
            pq.push({i, dist[i]});

        // dijkstra
        while (!pq.empty()) {
            pair<int, int> curr = pq.top();
            pq.pop();

            //边界检查
            //如果当前节点已访问，跳过
            if (flag[curr.first])
                continue;
            //如果当前节点的距离为INF，则该节点距离没有更新过，跳过
            if (curr.second == INF)
                continue; 
            //如果已记录的距离小于当前读到的距离，则当前不是一个有效节点，跳过
            if (dist[curr.first] < curr.second)
                continue;
            flag[curr.first] = true;

            for (auto point : graph[curr.first]) {
                if (flag[point.first])
                    continue;

                //更新距离、前驱节点和优先队列
                if (curr.second + point.second < dist[point.first]) {
                    dist[point.first] = curr.second + point.second;
                    pre[point.first] = curr.first;
                    pq.push({point.first, dist[point.first]});
                }
            }
        }

        int res = -1;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF)
                return -1;
            else
                res = res > dist[i] ? res : dist[i];
        }
        return res;
    }
};

分层Dijkstra

分层的核心在于拆点，在原本的状态上增加一维以记录当前所在的层数，用于存储数据的dist和pq也需要各自增加一维。

模板题

题目链接：[P4568 JLOI2011] 飞行路线 - 洛谷

点击展开题目

P4568 [JLOI2011] 飞行路线

题目描述

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 \(n\) 个城市设有业务，设这些城市分别标记为 \(0\) 到 \(n-1\)，一共有 \(m\) 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 \(k\) 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

输入格式

第一行三个整数 \(n,m,k\)，分别表示城市数，航线数和免费乘坐次数。

接下来一行两个整数 \(s,t\)，分别表示他们出行的起点城市编号和终点城市编号。

接下来 \(m\) 行，每行三个整数 \(a,b,c\)，表示存在一种航线，能从城市 \(a\) 到达城市 \(b\)，或从城市 \(b\) 到达城市 \(a\)，价格为 \(c\)。

输出格式

输出一行一个整数，为最少花费。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

输出 #1

1
8

说明/提示

数据规模与约定

对于 \(30\%\) 的数据，\(2 \le n \le 50\)，\(1 \le m \le 300\)，\(k=0\)。

对于 \(50\%\) 的数据，\(2 \le n \le 600\)，\(1 \le m \le 6\times10^3\)，\(0 \le k \le 1\)。

对于 \(100\%\) 的数据，\(2 \le n \le 10^4\)，\(1 \le m \le 5\times 10^4\)，\(0 \le k \le 10\)，\(0\le s,t,a,b < n\)，\(a\ne b\)，\(0\le c\le 10^3\)。

另外存在一组 hack 数据。

点击展开代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

//分层 无向 dj

struct Point{
    int u;
    int dist;
    int k;
};

struct compare{
    bool operator()(Point a,Point b){
        return a.dist>b.dist;
    }
};

const int MAX=1e4+5;
const int K=15;
const int INF=0x3f3f3f3f;
int n,m,k,u,v,c,s,t;
vector<pair<int,int>> graph[MAX];   //target,dist
int cost[MAX][K];      //target to orig ,layer
bool isVis[MAX][K];
priority_queue<Point,vector<Point>,compare> pq; 

int main(){
    cin>>n>>m>>k>>s>>t;
    for(int i=0;i<m;i++){
        cin>>u>>v>>c;
        graph[u].push_back({v,c});
        graph[v].push_back({u,c});
    }

    //init
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            cost[i][j]=INF;
        }
    }
    cost[s][0]=0;
    pq.push({s,0,0});

    //dj
    while(!pq.empty()){
        Point curr=pq.top();
        pq.pop();
        if(isVis[curr.u][curr.k])continue;
        isVis[curr.u][curr.k]=true;

        for(auto point:graph[curr.u]){
            //循环两次，j=0，1，分别表示付费和免费。
            for(int j=0;j<2;j++){
                if(curr.k+j>k)continue;
                if(isVis[point.first][curr.k+j])continue;
                if(cost[point.first][curr.k+j]<=curr.dist+point.second*(1-j))continue;

                int newdist=curr.dist+point.second*(1-j);
                if(newdist<cost[point.first][curr.k+j]){
                    cost[point.first][curr.k+j]=newdist;
                    pq.push({point.first,newdist,curr.k+j});
                }
            }
        }
    }

    int res=INF;
    for(int i=0;i<=k;i++){
        res=min(res,cost[t][i]);
    }
    cout<<res;

    return 0;
}