总论
最短路算法是常用的图论算法，实现多种多样，且拓展度很好，值得学习，现在指的最短路都是单源最短路。
前置芝士
存图：
- 邻接矩阵
- 邻接表
- 链式前向星（数组模拟链表）
这是练习。
三角形不等式：
对于一个图 $G$，记 $G[i][j]$ 为从 $i$ 到 $j$ 的最短路，则对任意的 $k$，有 $G[i][j]<G[i][k]+G[k][j]$ 。
证明的话很简单，就是定义呗。
不会去手搓数据去。
算法
Floyd
思想基于动规，分别遍历所有点，经过每一个点 k 是否满足三角形不等式，代码复杂度 $O(n^3)$
1
2
3
4
5
6
7
| for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
}
}
}
|
SPFA
它死了。，思想其实就是 Bellman-Ford，考试慎用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| struct node{
int to,next,value;
}e[N*50+10];
void spfa(int s){
memset(d,0x3f,sizeof d);
vis[s]=1;
d[s]=0;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(d[y]>d[x]+e[i].value){
d[y]=d[x]+e[i].value;
if(!vis[y]){
q.push(y);
vis[y]=1;
}
}
}
}
}
|
代码神似BFS。
Dijkstra
目前最优秀的算法，但无法处理负边权，因为其基于贪心算法，优化后复杂度为 $O(mlogm)$，这个板子一定要熟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void dij(int s){
memset(d,0x3f,sizeof d);
d[s]=0;
q.push({s,0});
while(!q.empty()){
int x=q.top().num;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(d[y]>d[x]+e[i].value){
d[y]=d[x]+e[i].value;
q.push({y,d[y]});
}
}
}
}
|
有两个点要注意一下：
- 初始入队是不需要标记是否访问，不然 while 循环不会启动。
- 标记的是取出的堆头，不是别的