封面来源

Pixiv THEM-95671915

浅谈最短路算法

Floyd

  • 复杂度较高（也就3个for循环）
  • 不能有负环
  • 多源最短路（跑一遍后所有点间的最短路都出来了）
  • 就是个暴力

思路

对于一个点对​来说，如下图，的最短路是​,这就是Floyd的中心思想

graph
graph

核心代码

cpp
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]);
        }
    }
}

但是显然第一维对结果无影响，所以可以简化为一个二维数组

综上，时间复杂度为,空间复杂度为

Bellman-Ford

  • 支持负边权
  • 单源最短路
  • 可以优化为SPFA

思路

设源点为

​​表示​​的最短路

操作指

不就是上面的那个三角形不等式吗?

那么Bellman-Ford算法如下

fallback
while(1) for each edge(u,v) relax(u,v);

当一次循环中没有松弛操作成功时停止

核心代码

fallback
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);
	}
}

复杂度为

队列优化版Bellman Ford: SPFA

原名Shortest Path Faster Algorithm（太自信了

减少一些无用的松弛操作，只有上一次被松弛的点所连的边才可能引起下一次松弛，用队列维护哪些节点可能会引起松弛操作，就只用访问必要的边了

代码

cpp
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;
                }
            }
        }
    }
}

复杂度

Dijkstra

发音/ˈdikstrɑ/（

  • 非负权图

思路

BFS

代码

cpp
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));
			}
		}		
	}
}

复杂度为