【算法笔记】最短路

前言

因为发现自己对好多算法的理解都不深，所以想起来写这么个东西。

一些基础的东西

我们每一次设的 \(dist\) 都是“对于最短路径的估计”。

也就是说它最先是不确定的。

只有当我们求了最短路过了之后它才真正是“最短路径”。
关于松弛

说白了就是这样子的一个图：

我们对于任意的 \(u,v\) ，如果 \(dist[s -> u] > dist[s->v]+w[v->v]\)
也就是说存在新的更短的路径那么就更新估计。

SSSP

SSSP(单源最短路径)是求从源点 \(s\) 到其它所有点的最短路径问题。

也可以说是：对在权图 \(G=(V,E)\),从一个源点 \(s\) 到汇点 \(t\) 有很多路径，其中路径上权和最少的路径，称从 \(s\) 到 \(t\) 的最短路径。

一般常用的有几种算法：

Dijkstra
SPFA
Bellman-ford
Floyd

那么，先从最基础也是最实用的 Dijkstra 说起。

Dijkstra 算法：

定义&过程：

该算法于 1959 年由荷兰的计算机科学家 Dijkstra 发明。

简单来说还是基于SSSP最基础的思想：松弛。

Dijkstra采用贪心算法的策略。

他每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

根据我们松弛的三角形不等式：

\[dist[x] + w[x][y] >= dist[y] \]

这个算法主要分为以下的几个步骤：

将我们的顶点集合 \(V\) 分成两个部分：\(S\) 和 \(T\) ，定义 \(S\) 是已经求出（就是跑过的）的顶点集合（开始的时候只有一个点，就是源点 \(s\)），对于 \(T\) : \(V-S =T\) （就是剩下的部分）
将 \(T\) 中的所有元素依次（按编号递增）加入到 \(S\) 里面。保证以下两个条件：

\(\alpha\) : 源点到 S 中的任意一个点的距离都不大于源点到 T 中的任意一个点的最短路长度。

\(\beta\) ： S中的点的 dist = 源点到这个点的距离，T中的点的 dist = 从源点到这个点的最短路长度，且中间经过的点只有在S中的顶点。

那么有一个结论：

源点到 \(T\) 中顶点的，或是从源点到\(T\) 中顶点的直接路径的权值；或是从源点经过 \(S\) 中的顶点到该顶点的路径权值之和。

不过这里有一个更加易于理解的过程：

1. memset(dist,INF,sizeof(dist);

2. dist[s]=0;

3.找出一个没有被标记的节点 v，标记一下。

4.对于每个和 v 相连的节点，如果它满足三角形不等式，更新。

5. 直到所有点都被标记。

但是这个算法的复杂度是 \(\text{O}(n^2)\) 的。

根据它贪心的本质，有了用堆优化的方法。

对于它的实现是这样的：

将源点 \(s\) 加入堆。
取出堆顶，维护一下堆的性质。
我们从这个堆顶的点出发，利用三角形不等式去松弛和它相邻的所有点。如果它不在堆里（以前没访问过），就加入堆，并更新 dist。
如果它已经在堆里了，也就是说从源点到这个点有更短的路径（以前来过），更新dist
如果我们的堆顶取出来的时候是终点 \(t\) 了，根据贪心策略，可以知道这个时候就已经有了最短的路径，不会再有更短的了，结束。

（当然如果是求整个图的 \(dis\) ，就直接到堆为空（所有点被标记）停止就可以了）

例题：

P4779 【模板】单源最短路径（标准版）
P3371 【模板】单源最短路径（弱化版）

（上面的两道题都可以用dij过掉）

代码：


#include
using namespace std;

const int si=2e6+2;
int n,m,s;
vector >g[si];
priority_queue >q;
int dis[si];

int main(){
    cin>>n>>m>>s;
    for(register int i=1,x,y,z;i<=m;++i){
        cin>>x>>y>>z;
        g[x].push_back(make_pair(y,z));
       // g[y].push_back(make_pair(x,z));
    }
    for(register int i=1;i<=n;++i){
        dis[i]=1e9;
    }
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        register int x,y;
        x=q.top().second;
        y=-q.top().first;
        q.pop();
        if(dis[x]!=y){
            continue;
        }
        for(register int i=0,to,val;idis[x]+val){
                dis[to]=dis[x]+val;
                q.push(make_pair(-dis[to],to));
            }//松弛
        }
    }
    for(register int i=1;i<=n;++i){
        cout<



bellman-frod & SPFA
这两个算法对我来说其实一般是用来判断负环的，所以简单讲一下。
Bellman-定义
\(\text{bellman}\) 是基于迭代思想的算法。
做法十分简单。
扫描所有边，如果 \(dist[y] > dist[x] + w[x][y]\) ,那么用 \(dist[x] + w[x][y]\) 更新 \(dist [y]\) 。直到它没有更新操作发生。
说白了就是个暴力（
很明显的，它的复杂度是 \(O(nm)\) 级别的。
SPFA-定义
而 \(\text{SPFA}\) ， 则是对\(\text{bellman}\)的一个队列优化。
这个队列里的元素是“有更新潜力的”。
也就是说它可能还能更新。
所以每次松弛扩展的时候就把索扩展的元素放进队即可。
开始的时候会有一个队列，让源点处在其中。
每次执行\(\text{bellman}\)的那种松弛操作之后，将其放入队列，直到队列是空的为止（没有有更新潜力的元素）。
但是 \(\text{SPFA}\) ，常常成为毒瘤出题人卡的主要对象。
（在随机图上是比较优秀的，但是如果出题人构造了一个菊花图一类的东西……那您就可以原地去世了）。
例题：


P3371 【模板】单源最短路径（弱化版）


P4768 [NOI2018]归程


（当然，如果您用堆优化Bellman-Frod，那么它和Dij就没有本质上的差别了。）
代码（P3371）：

#include
using namespace std;

const int si_e=1e6+10;
const int si_n=1e5+10;

int n,m,tot=0,s;
struct node{
	int Next,ver,w,head;
}e[si_e];
int dist[si_n];
bool vis[si_n];
queueq;

void add(int u,int v,int w){
	e[++tot].ver=v,e[tot].w=w;
	e[tot].Next=e[u].head,e[u].head=tot;
}

void SPFA(int s){
	memset(dist,0x3f,sizeof dist);
	memset(vis,false,sizeof vis);
	dist[s]=0,vis[s]=true;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(register int i=e[u].head;i;i=e[i].Next){
			int v=e[i].ver,w=e[i].w;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				if(!vis[v]) q.push(v),vis[v]=true;
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(register int i=1,u,v,w;i<=m;++i){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	SPFA(s);
	for(register int i=1;i<=n;++i){
		cout<

关于SPFA和Bellman判断负环
Bellman：
如果经过 \(n\) 轮迭代，迭代仍然未结束，那么就没有负环。
如果在 \(n-1\) 轮之内结束了，那么就有负环。
（下面是我一两个月以前写差分约束的时候写的\(\text{bellman}\)判负环）
（这个东西在差分约束里面很有用）

bool bellman_ford(int n,int m){
    for(register int i=1;i<=n;++i){
        dist[i]=0;
    } 
    for(register int i=1;i<=n;++i){
        for(register int j=0;jdist[e.from]+e.dist){
                dist[e.to]=dist[e.from]+e.dist;
            }
        }
    }
    for(register int j=0;jdist[e.from]+e.dist){
            return false;
        }
    }
    return true;
}



SPFA
假设 \(cnt[x]\) 表示 \(1\) 到 \(x\) 的最短路里有多少边。
且 \(cnt[1] = 0\) 。
在松弛的时候，更新一下 \(cnt[]\) 。
那么怎么更新?
\(cnt[y]=cnt[x]+1\)。
如果更新的时候， $n \le cnt[y] $ ，那么就有负环。
反之则亦然。
\(\text{SPFA}\) 就不放代码了。
其实和上面的 \(\text{bellman}\) 差不多。
当然还有一种办法是判一个点的入队次数。

附：关于负边权处理



算法
能否处理负边权




\(\text{Dijkstra} -\text{O}(n^2)\)
不行


\(\text{HeapDij} - \text{O}(m \log n)\)
不行


$\text{SPFA} -\text{O}(nm/km) $
可以


\(\text{Bellman-Ford} - \text{O}(nm)\)
可以



（您会发现，所有基于贪心的算法都不行，您可以想一想为什么（这应该很好想））。

Floyd
本质上来说，\(\text{floyd}\) 是一个动态规划算法。
它能够在 \(\text{O}(n^3)\) 的复杂度里解决任意两点之间的最短距离问题。
而且一般图比较稠密。
假设 \(f[k][i][j]\) 表示经过一些编号不超过k的节点，从i到j的最短路长度
（当然这个k是可以改定义的）
考虑如何转移。
因为是dp，所以\(k\)这个状态可以从 \(k-1\) 转移过来。
然后从 \(i\) 到 \(j\) 可能是直接过去（不是只有一条边，而是 \(f[k-1][i][j]\) 这个状态）。
也可能先从 \(i\) 到 \(k\) 再到 \(j\) （\(f[k-1][i][k]+f[k-1][k][j]\)）
然后转移方程就出来了。
\[f[k][i][j]=\min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])
\]
不过注意在写循环的时候，k要放在最外层。
因为它代表“阶段”，如果不是第一层那么转移顺序会炸开来。
至于初始化。用邻接矩阵就可以了。
根据定义 :\(f[0][i][j]=a[i][j]\) ,然后跑一个 \(n^3\) 的DP就行了。
当然因为转移的时候 \(k\) 只会从 \(k-1\) 转移而来。
所以也可以和背包一样滚动数组把第一维滚掉。
也就是：
\[f[i][j]=\min(f[i][j],(f[i][k]+f[k][j]))
\]
代码：

#include
using namespace std;

const int si=4e2+10;
int n,m;
int f[si][si];

int main(){
	cin>>n>>m;
	memset(f,0x3f,sizeof f);
	for(register int i=1;i<=n;++i){
		f[i][i]=0;
	}
	for(register int i=1,u,v,w;i<=m;++i){
		cin>>u>>v>>w;
		f[u][v]=min(f[u][v],w);
	}
	for(register int k=1;k<=n;++k){
		for(register int i=1;i<=n;++i){
			for(register int j=1;j<=n;++j){
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	//f[i][j]=dis[i][j]; 
	return 0;
}

传递闭包
给定若干的元素和若干对二元关系。
在关系具有传递性的情况下，推导出更多的二元关系。
这就是传递闭包。
比如给你 \(a,b,c\)
且 \(a
那么你就要通过关系推出 \(a
我们可以用 \(\text{floyd}\) 原理解决。
设 \(f[i][j]=true\) 表示i和j有一个关系。
反之则没有。
且 \(f[i][i]=true\)
比如在上面的例子里就是 \(f[a][b]=1,f[b][c]=1\)
然后跑一遍\(\text{floyd}\)。
在转移的时候将所有可以推出的关系更新即可。
最长路
一般使用SPFA（因为需要负数）。
我们只需要把所有边权改成负数跑SPFA即可。
（dis初始化还是正无穷）。
然后取出来给dis取绝对值即可。
（当然如果图中有负边那就要小心点，如果全是正边就直接改）。

练习题：

P1119 灾后重建
P1629 邮递员送信
P1144 最短路计数
P1462 通往奥格瑞玛的道路
P1522 [USACO2.4]牛的旅行 Cow Tours


Bellman_Ford的证明

经过一轮松弛，从起点出发到某个相邻点\(u\)的最短路径一定会被确定下来。（不可能出现：所有点都还不是最短路径值）
再经过一轮松弛，从 \(u\) 出发到某个相邻点\(v\)的最短路径一定会被确定下来。
不含有负环的图中，一条简单路径最多 \(n\) 个点，\(n-1\) 条边。
最多经过 \(n-1\) 轮松弛，便可以把到最远的点的最短距离确定下来。
\(n-1\) 轮必然就能把最远点的最短路径确定下来，最远点的最短路径都确定下来了，其他点肯定在之前已经确定最短路径值。

Dijsktra的证明

没有负边权，那么路径值最小的点，就不可能在后续的过程中更新，将其染色。
比如起点的路径值为 \(0\)，这个值就不可能被更新，所以先染色。
因为每步都是走正边权，从其他路径绕过来，肯定路径值必然增加。
被确定的最小值点，既然已经比其他点值小，就不可能从其他点迂回后更新它。
所以每步的最小值，一定是路径值最小的时候，立即染色，不可能在后边更新了。

算法	能否处理负边权
\(\text{Dijkstra} -\text{O}(n^2)\)	不行
\(\text{HeapDij} - \text{O}(m \log n)\)	不行
$\text{SPFA} -\text{O}(nm/km) $	可以
\(\text{Bellman-Ford} - \text{O}(nm)\)	可以


						
							

						
							
							
			Algor-最短路Cate-图论Type-算法笔记

【算法笔记】最短路

前言

一些基础的东西

SSSP

Dijkstra 算法：

定义&过程：

例题：

代码：

bellman-frod & SPFA

Bellman-定义

SPFA-定义

例题：

代码（P3371）：

关于SPFA和Bellman判断负环

Bellman：

SPFA

附：关于负边权处理

Floyd

代码：

传递闭包

最长路

练习题：

Bellman_Ford的证明

Dijsktra的证明

相关

标签