单源正权最短路径——Dijkstra算法

• 问题引入
• 思路一览
• 算法原理
• code

问题引入

给出n点m边，其中边的权值皆为非负数，要求快速给出一个点到其余点的最短距离

思路一览

• dfs遍历维护最短距离
• floyd算法算全源最短，但是这玩意时间复杂度O(n³)，最多也就1000个点左右
• 主角Dijkstra算法

算法原理

主要是以源点为根节点逐步构建一棵最短路径树，也就是从未加入最短路径树的结点中选择最短的与树相连的边加入最短路径树，总的来说还是一种贪心的思想，Dijkstra算法生效的条件或者有两条，一是边权要全部都是正边权，不能存在负边权，不然贪心就不成立，二是源点和某一结点的路径上的点一定是最短路径，假设存在源点u，终点v存在一条最短路径和中继结点mid，假设存在一条由u到mid的更短路径，那么该uv的最短路径便不成立，因为u可以从另外那条到mid的更短路径到达mid结点，再到达v结点(该条证明的前提是第一个条件)。
根据上面两个原理就可以这样操作得到源点到其他结点的最短距离：首先将与源点直接相连的结点加入集合w中，然后从中选择不在树上的最短的边，接着将加入结点的相连边加入集合，继续选，直到集合为空，在选择过程中要及时更新已经在树上的结点。分析时间复杂度就是发现每次在集合中找最短边的过程最耗时，所以选择用集合或者小根堆优化程序。

code

int n, m, k, vis[N], dis[N];
vector<pii> e[N];
priority_queue<pii, vector<pii>, greater<pii>> w;
void Dijkstra(int cur) {
    memset(dis, 127, sizeof dis);
    //初始条件
    w.push({0, cur});
    while(!w.empty()) {
        while(!w.empty() && vis[w.top().second]) w.pop();
        if(w.empty()) break;
        //其实这里还可以加入一个跳出条件，参照prim算法构建最小生成树
        //加一个最短路径树上的结点值cnt，当cnt==n时跳出
        int curDis = w.top().first, cur = w.top().second;
        vis[cur] = 1, dis[cur] = curDis;
        for(auto z:e[cur]) {
            int nxt = z.first, addDis = z.second;
            if(!vis[nxt]) w.push({addDis+curDis, nxt});
        }
    }
}