Catshao

用户名：Catshao

访问量：28830

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

值域分块题解
浏览：221

此题极度卡常
浏览：34

区间逆序对（弱化版）
浏览：158

你可能喜欢

数据结构-Dijskra堆优化详解（C++）（小白向）

　　作者: Catshao　　　　发表时间：2021-01-30 19:22:59 浏览：922　|　评论：0　

原题链接：数据结构-Dijskra(迪杰斯特拉)最短路径算法

在看这篇文章之前，你需要学会如何存储图，本文所用为邻接表。[百度一下](https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E8%A1%A8/9796152?fr=aladdin)

### 概述
dij是一种快速求单源最短路径的贪心算法。单源，即为一个起点，到图中其他的点的最短路。

### 未优化的dij
1. 创建一个dis表，将每一个节点到起点的距离记录下来。初始化时每一个距离都是无限大，这里可以用climits中的 INT_MAX或LLONG_MAX来代替无限。
2. 创建一个mark表，存储每一个点是否枚举过，初始化为false。
3. 更新起点四周的节点的距离。（起点可以直接到这些点）

**进入大循环**
1. 枚举dis表，寻找距离离起点最近的节点。
2. 更新节点四周的距离。

下面两篇文章，通过图文与动画的方式，让你更直观地感受dij的过程。

#####[程序员小灰 - 单源最短路](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653197626&idx=1&sn=fca7472af006a7f8890ee84ad7cf1116&chksm=8c99e7e0bbee6ef6faa1a34160a5e135503425e37552e90dfca2fbc10f223dbf3b875e84e418)

##### [dij可视化（速度可以调慢）](https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html)

### 堆优化的dij
看过上面的过程，我相信大家都有了初步的了解。但是，我们不妨计算一下，枚举n个节点，在每一次枚举中我们还需要从n个节点中找到最大的（贪心）来枚举，所以时间复杂度为**n^2**。

若想优化，可以从找最大值来入手。

这里可以用小根堆来解决寻找最大值的问题。二叉堆每一次调整（插入和删除）时间复杂度为**logn**，找最大值为常数，简化后的dij速度可达**nlogn**

##### [二叉堆可视化](https://www.cs.usfca.edu/~galles/visualization/Heap.html)

这里放一下蒟蒻的小根堆模板

```cpp
//
// Created by Cat-shao on 2021/1/15.
// 小根堆模板
#include <vector>
using namespace std;

template<typename T>
class heap // 小根堆模板
{
public:
    int length;
    vector<T> tree;

heap () {
        clear();
    }

bool empty() {
        return length <= 0;
    }

void clear() {
        tree.clear();
        tree.resize(1);
        length = 0;
    }

void push(const T &x) {
        if (length == tree.size() - 1) {
            tree.resize(tree.size() * 2);
        }
        int index = ++ length;

for (; index > 1 && x < tree[index / 2]; index /= 2) { // n / 2为父节点，n/=2即为n到父节点，n > 1为n不是根节点
            tree[index] = tree[index / 2]; // 将父节点的值付给自己
        }

tree[index] = x; // x 上去
    }

void pop() {
        if (empty()) {
            return;
        }

tree[1] = tree[length --];
        percolateDown(1);
    }

void percolateDown(int index) {
        T x = tree[index];
        int childIndex;

for (; index * 2 <= length; index = childIndex) {
            childIndex = 2 * index; // 子节点 = 2k 或 2k+1
            if (childIndex != length && tree[childIndex + 1] < tree[childIndex]) { // 右节点合法并且比左节点小
                childIndex ++;
            }
            if (tree[childIndex] < x) {
                tree[index] = tree[childIndex]; // 父节点、子节点互换
            } else {
                break;
            }
        }
        tree[index] = x;
    }

int size() {
        return length;
    }

T top() {
        return tree[1];
    }

T front() {
        return tree[1];
    }
};
```

在考场上打一个这么长的（雾）小根堆费时费力。stl库中的优先队列是大根堆，所以我们可以在定义edge的时候重载<运算符，来实现小根堆的效果（这也是我不用pair的原因）

### dij记录路径

有些题目要求我们输出最短路的路径，我们可以使用一个数组path来存储当前节点的前一个节点，这样我们就可以像链表一样，一个一个追踪，获取路径。

说了这么多，来看下代码吧。
其中DEBUG非必须，可以用来调试。这是我的代码风格，希望每一个人都拥有自己独有的风格。
```cpp
//
// Created by Cat-shao on 2021/1/29.
//

#include <cstdio>
#include <deque>
#include <set>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
const int MAXN = 100;

class edge
{
public:
    int id;
    long long cost;
    edge(int i, long long c) {
        id = i;
        cost = c;
    }

edge() {
    }

bool operator < (const edge &p)const{
        return cost > p.cost;
    }

bool operator > (const edge &p)const{
        return cost < p.cost;
    }
};

deque<edge> mp[MAXN]; // 接临表，set顺序为由大到小
long long dis[MAXN];
int path[MAXN]; // 距离
bool mark[MAXN]; // 标记
priority_queue<edge> q; // 大根堆（edge已经重定义，可以当做小根堆使用，顺序为由小到大）
int n, s = 1;

class debuger
{
public:
    void printDEBUGTag() {
        printf("[DEBUG]");
    }

void printGraph() {
        for (int i = 1; i <= n; ++i) {
            printDEBUGTag();
            printf("Point:%d {", i);
            for (deque<edge>::iterator it = mp[i].begin(); it != mp[i].end(); it++) {
                printf("%d->%d %d, ", i, it->id, it->cost);
            }
            printf("}\n");
        }
    }

void printDistance() {
        printDEBUGTag();
        for (int i = 1; i <= n; ++i) {
            if (dis[i] != LLONG_MAX) {
                printf("%d->%d %d, ", n, i, dis[i]);
            }
        }
        printf("\n");
    }

void printQSize() {
        printDEBUGTag();
        printf("QSize:%d\n", q.size());
    }

void printPath(int index) {
        printDEBUGTag();
        deque<int> output;
        while (index != s) {
            output.push_front(index);
            index = path[index];
        }
        output.push_front(s);

while (!output.empty()) {
            printf("%d ", output.front());
            output.pop_front();
        }
        printf("\n");
    }

void outputPath(int index) {
        deque<int> output;
        if (dis[index] == LLONG_MAX) {
            printf("-1\n");
            return;
        }
        while (index != s) {
            output.push_front(index);
            index = path[index];
        }
        output.push_front(s);
        while (!output.empty()) {
            printf("%d ", output.front());
            output.pop_front();
        }
        printf("\n");
    }

void outputPathLen(int index) {
        int cnt = 0;
        while (index != s) {
            index = path[index];
            cnt++;
        }
        printf("%d\n", cnt);
    }

void outputDistance() {
        for (int i = 1; i <= n; ++i) {
            printf("%d ", dis[i]);
        }
        printf("\n");
    }
};
debuger DEBUG;
void dijkstra()
{
    // 初始化dis（距离）数组和mark（标记）数组
    for (int i = 1; i <= n; ++i) {
        dis[i] = LLONG_MAX; // 默认距离为INF
    }
    memset(mark, 0, sizeof(mark));
    memset(path, 0, sizeof(path));
    mark[s] = true; // 标记起点
    mark[0] = true; // mark[0]标记true，0不是任何节点
    dis[s] = 0; // 起点到自己距离为0
    while (!q.empty()) { // 清空队列
        q.pop();
    }
//    DEBUG.printGraph();

// 遍历起始节点的路径，更新dis
    for (deque<edge>::iterator it = mp[s].begin(); it != mp[s].end(); it++) {
        if (it->cost < dis[it->id]) {
            dis[it->id] = it->cost; // 有可能出现对于两个节点中出现多条节点，故需要用min来选择最近的
            path[it->id] = s;
        }
    }
    // push到队列中
    for (int i = 1; i <= n; ++i) {
        if (dis[i] != LLONG_MAX) { // 如果为LLONG_MAX则节点并未经过遍历，不需要push到队列中
            q.push(edge(i, dis[i])); // 此处起点为s（n），终点为i，距离为dis[i]
        }
    }
//    DEBUG.printDistance();
//    DEBUG.printQSize();

while (!q.empty()) {
        int index = q.top().id;
        while (mark[index]) { // 重复寻找，直到mark[index] 为false（index节点未标记）或队列为空
            q.pop();
            if (!q.empty()) {
                index = q.top().id;
            } else {
                break;
            }
        }
        if (q.empty()) { // 如果队列为空，则要么图被遍历完，或者图不连通，此二种情况均应退出
            break;
        }
        q.pop();
        mark[index] = true; // 标记当前遍历节点
        for (deque<edge>::iterator it = mp[index].begin(); it != mp[index].end(); ++it) {
            if (dis[index] + it->cost < dis[it->id]) {
                dis[it->id] = dis[index] + it->cost;
                path[it->id] = index;
                q.push(edge(it->id, dis[it->id]));
            }
        }
    }
}

int main()
{
    int m;
    scanf("%d%d", &n, &s);
    s++;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &m);
            if (m) {
                mp[i].push_back(edge(j, m));
            }

}
    }

dijkstra();
    for (int i = 1; i <= n; ++i) {
        if (i == s) {
            continue;
        }
        printf("%d ", dis[i]);
    }
    return 0;
}
```

> ### 其他优化
可以用stl的set来优化，本质为红黑树，优化后复杂度为nlogn。
也可以用线段树来优化dij。

------------

若文章有什么疏漏请在评论区指出。

参考：
* [小灰 最短路](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653197626&idx=1&sn=fca7472af006a7f8890ee84ad7cf1116&chksm=8c99e7e0bbee6ef6faa1a34160a5e135503425e37552e90dfca2fbc10f223dbf3b875e84e418)
* [算法可视化](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

宏定义（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

数据结构-Dijskra堆优化详解（C++）（小白向）

评论区

精彩推荐

母牛的故事（C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

弟弟的作业（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

IP判断（C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

宏定义（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

数据结构-Dijskra堆优化详解（C++）（小白向）

评论区

精彩推荐

母牛的故事 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

弟弟的作业 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

IP判断 （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

　　评论区

母牛的故事（C语言代码）

弟弟的作业（C++代码）

IP判断（C语言描述，蓝桥杯）