【备战蓝桥杯系列】单源最短路径Dijkstra算法模板

Dijkstra算法模板

蓝桥杯中也是会考到图论最短路的，一旦考到，基本是不会太难的，只要知道板子就基本能拿分了。

两个板子如下

朴素Dijkstra算法

适应情况：稠密图，正权边

时间复杂度 O(n^2 + m)

int dijkst(){
    memset(dist, 0x3f, sizeof dist);//初始化成无穷大
    dist[1] = 0;
    for(int i = 1; i <= n; i ++ ){//寻找所有点到起点的最短距离
        int t = -1;
        for(int j = 1; j <= n; j ++ ){//找到未确定且距离最小的点
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;
        }
        st[t] = true;//将该点确定
        for(int j = 1; j <= n; j ++ ){//用该点距离更新其他点
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

堆优化版dijkstra

适应情况：稀疏图，正权边

时间复杂度 O(mlongn) — 堆每次更新值时间复杂度是logn，而通过邻接表来存，

​ 每次只遍历与该点相连的边，所以总的遍历次数是m，故时间复杂度是mlogn

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>,greater<PII>> heap;
    heap.push({0, 1});
    while(heap.size()){//第一步遍历
        auto t = heap.top();//第二步①找出未确定的距离最小的点
        heap.pop();
        int dis = t.first, ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;//第二步②将该最短距离确定下来
        for(int i = he[ver]; i != -1; i = ne[i]){//第三步 更新dist数组
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
                //此处会产生冗余，对于产生新的最短距离的点，其{旧值距离，点}会成为冗余数据，
                //下沉到堆得下半部分
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24