(本人很菜，有错请指出，违规了我删，orz各位大佬

最短路问题

给定一张图，$n$个点，$m$条边，源点（出发点)$s$

求$s$点到其余点的最短距离

此处设$dis[u]$为$s \rightarrow u$的最短距离

$dijkstra$

$dijkstra$是一种优秀的最短路算法

采取的是贪心的思想

代码

先贴下代码

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
struct node{
	int w,to;
	bool operator<(const node &t)const{
		return w>t.w;
	}
};
int n,m,s;
int dis[N];
priority_queue<node>q;
vector<node>e[N];
void dijkstra(){
    q.push((node){0,s});
    for(int i=1;i<=n;i++) dis[i]=1e9;
    dis[s]=0;
    while(!q.empty()){
        node f=q.top();
		q.pop();
        if(f.w!=dis[f.to]) continue;
        for(node g:e[f.to]){
        	int v=g.to,w=g.w;
            if(dis[v]>dis[f.to]+w){
            	dis[v]=dis[f.to]+w;
            	q.push((node){dis[v],v});
			}
        }
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&s);
    int u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back((node){w,v});
    }
    dijkstra();
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
    return 0;
}

贪心原理

• 在正权图中，已经确定最短距离的点不会再被更新

• 每次通过该点进行松弛，则必可拓展出一个新的确定最短距离的点

• 每次重复上一过程，则可遍历整个图，确定所有点的最短路

朴素算法

每次选取全局距离最小点进行拓展，直到遍历完整张图

堆优化：

概述：

朴素算法中选取全局最小点进行拓展,即在$n$个数中求最小值

每次只有被松弛成功的点的$dis$值会被改变，单独对这些点进行更新即可

两种操作：

1. 单点修改

2. 求全局最值

数据结构的选择

1. 堆

2. 线段树

3. 树状数组

4. $……$

总之就是选一个能实现上述两种操作的数据结构随便维护一下就行了

不过一般选择堆，因为可以用std::prioority_queue,好写，易调

$priority\_queue$

不过优先队列不能直接更改元素的值

于是，每次将松弛成功的点入队

这些点可能为更新前还在堆中，则采取惰懒删除的方式将其删除

于是，删除旧节点，加入新节点，达到了单点修改的效果

至于最值就简单了，直接取出堆头

惰懒删除

所谓惰懒删除，即忽视队中不要的元素

具体实现就是这一句

if(f.w!=dis[f.to]) continue;

此处f点是堆头

f.w是$s \rightarrow f.to$的最短距离，但不一定是当前的

dis[f.to]是$s \rightarrow f.to$的最短距离，是当前的

如果f.w==dis[f.to]则f是最新拓展的

否则，f就过时了，属于不要的元素

对于$\forall v \in G<n,m>$，过时点肯定不如最新的点（因为更新条件是dis[v]>dis[f.to]+w)

于是也可以采取标记法（参照第一篇题解），可能更好理解：

已经确定了最短$dis$的$v$不再更新，确定它是最小值后有关此节点的f也全部删除

二者是等同的

(还可以发吗qwq)