封面来源
Pixiv THEM-95671915
浅谈最短路算法
Floyd
-
复杂度较高（也就3个for循环）
-
不能有负环
-
多源最短路（跑一遍后所有点间的最短路都出来了）
-
就是个暴力
思路
对于一个点对$(s,t)$来说，如下图，$1 \to 2$的最短路是$ 1\to 3 \to 2$,这就是Floyd的中心思想
核心代码
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++){
f[k][x][y]=min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
}
}
}
|
但是显然第一维对结果无影响，所以可以简化为一个二维数组
$$
\begin{align*}
\begin{split}
f(i,j)=min(f(i,j),f(i,k)+f(k,j));
\end{split}
\end{align*}
$$
综上，时间复杂度为$O(N^3)$,空间复杂度为$O(N^2)$
Bellman-Ford
思路
设源点为$S$
$dis(t)$表示$S \to t$的最短路
$ relax(u,v)$ 操作指
$$
\begin{align*}
dis(v)=min(dis(v),dis(u)+len(u,v));
\end{align*}
$$
不就是上面的那个三角形不等式吗?
那么Bellman-Ford算法如下
1
|
while(1) for each edge(u,v) relax(u,v);
|
当一次循环中没有松弛操作成功时停止
核心代码
1
2
3
4
5
6
7
8
9
10
11
|
relax(u,v){
dis[v]=min(dis[v],dis[u]+len(u,v));
}
for(i,1,n){
dis[i]=len(S,i);
}
for(i,1,n){
for each edge(u,v){
relax(u,v);
}
}
|
复杂度为$O(NM)$
队列优化版Bellman Ford: SPFA
原名Shortest Path Faster Algorithm（太自信了
减少一些无用的松弛操作，只有上一次被松弛的点所连的边才可能引起下一次松弛，用队列维护哪些节点可能会引起松弛操作，就只用访问必要的边了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void spfa(int s){
queue<int> q;
FOR(i,1,n){
dis[i]=inf;
}
dis[s]=0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u]=0;
Graph(u){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
|
复杂度$O(N,M)$
Dijkstra
发音/ˈdikstrɑ/（
思路
BFS
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
voivoid dijk(int s){
for(int i=0;i<=n;i++)
dis[i]=inf,vis[i]=0;
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(make_pair(dis[s]=0,s));
while(!q.empty()){
pii t=q.top();q.pop();
int x=t.second;
if(vis[x])continue;
vis[x]=1;
Graph(x){
int v=e[i].v;
if(dis[x]+e[i].w<dis[v]){
dis[v]=dis[x]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
|
复杂度为 $O(m\log n)$
