Featured image of post 浅谈最短路算法

浅谈最短路算法

封面来源

Pixiv THEM-95671915

浅谈最短路算法

Floyd

  • 复杂度较高(也就3个for循环)

  • 不能有负环

  • 多源最短路(跑一遍后所有点间的最短路都出来了)

  • 就是个暴力

思路

对于一个点对$(s,t)$​来说,如下图,$1 \to 2$的最短路是$ 1\to 3 \to 2$​,这就是Floyd的中心思想

graph

核心代码
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

  • 支持负边权

  • 单源最短路

  • 可以优化为SPFA

思路

设源点为$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)$

所念皆星河
Built with Hugo
主题 StackJimmy 设计