最短路
记号约定
\(n\)是点数，\(m\)是边数。
\(s\)是源点。
\(D\left(u\right)\)是从\(s\)点到\(u\)点的实际最短路，\(D\left(u,v\right)\)是从\(u\)点到\(v\)点的实际最短路。
\(dis\left(u\right)\)是从\(s\)点到\(u\)点的即时最短路，\(dis\left(u,v\right)\)是从\(u\)点到\(v\)点的即时最短路。
\(w\left(u,v\right)\)是从\(u\)点到\(v\)点的边权值。
说明
由于全源最短路中的\(Johnson\)算法需要\(SPFA\)与\(Dijkstra\)的基础，所以先介绍单源最短路。
若一个图上存在负环，即负权边连成的环，就是负环。在有负环的图中，我们可以不断的绕着负环，所以最短路为\(-\infty\)。
单源最短路
单源最短路，是从一个源点到其余点的最短路。
\(SPFA\)
即\(Shortest\ Path\ Faster\ Algorithm\) （更快的最短路）
松弛操作
对于节点\(u\)，对于所有与\(u\)点相连的\(v\)节点，使\(dis\left(v\right)=\min\left(dis\left(u\right),dis\left(u\right)+w\left(u,v\right)\right)\)
这么做的目的是显然的，用\(s\to u\)的最短路去更新\(s\to v\)的最短路。
过程
我们发现只有被进行过松弛操作的节点才有用来松弛的价值，这是显然的，如果没有经过松弛，就没有可能更新最短路。
所以我们可以使用一个队列，将被松弛过的节点放入队列中，每次从队头取出节点进行松弛，最后队列为空，就表示最短路算法的结束。
在实际实现中，要判断是否存在负环。实际上，我们可以证明一个节点最多被松弛\(n\)次，所以在实现中，我们记录每个节点松弛的次数，就能判断出负权图。
性质
时间复杂度\(\Omega\left(km\right)\)或\(O\left(nm\right)\)，\(k\)为常数，一般为二。
由于代码中没有对最短路的不降要求，所以可以用于有负权边的图。
\(Code:\)
void SPFA(int s){
memset(dis,0x7f,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>dis[u]+val[i]){
dis[v]=dis[u]+val[i];
if(!vis[x]){
vis[v]=true;
q.push(v);
}
}
}
}
}
\(Dijkstra\)
\(Dijkstra\)只能用在非负权边的图上。
过程
将原图中的点分为两个集合，\(T\)所有未确定最短路的节点集合，\(S\)为已确定的集合，显然\(D\left(s\right)=dis\left(s\right)=0\)。
从源点开始，反复重复下列操作：
\(1.\)从\(T\)集合中取出最短路最小的节点\(u\)，放入集合\(S\)。
\(2.\)用\(u\)去松弛所有出边\(\left(u,v\right)\)。
直到\(T=\emptyset\)，算法结束。
正确性证明
\(T\)集合为未确定最短路的集合，移出\(T\)集合就意味着\(u\)点的最短路确定，即\(dis\left(u\right)=D\left(u\right)\)，证明的关键，就是证明只用一次松弛就能将最短路确定下来。
我们设\(k\)为当前操作次数。
命题：\(\forall k\in N_{+},D\left(u\right)=dis\left(u\right)\)
证明：
当\(k=1\)时，\(S=\left\{s\right\}\)，\(D\left(u\right)=dis\left(u\right)=0\)
设当\(k=l\)时成立，当\(k=l+1\)时：
记\(v\)点是\(l+1\)步时选择的节点，我们设\(v\)点是由\(u\)点松弛的，则\(u\in S\)，即\(D\left(u\right)=dis\left(u\right)\)。
若\(v\)点的最短路径不是\(s\to u\to v\)，则在\(v\)点的最短路径上有一个或多个节点\(\in T\)，即存在一条路径\(s\to x\to y\to v\)，其中\(y\)是路径上第一个不属于\(T\)集合的节点，\(x\)是\(y\)的前驱节点。
因为边权非负，有\(D\left(y\right)\le dis\left(y\right)\le D\left(v\right)\le dis\left(v\right)\)
由于当\(v\)节点被取出时，\(y\)节点没有被取出，所以\(dis\left(v\right)\le dis\left(y\right)\)
\(\therefore D\left(v\right)=dis\left(v\right)\)
\(\therefore s\to u\to v\)是\(v\)点的最短路
由数学归纳法得，命题成立。
性质
根据实现方式的不同，有不同的时间复杂度。
优先队列：\(O\left(m\log m\right)\)
\(Code:\)
struct node{
int num,dist;
bool operator <(const node &a)const{return dist>a.dist;}
node(int a,int b){
num=a,dist=b;
}
};
priority_queue<node>q;
void Dijkstra(int s){
memset(vis,false,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
dis[s]=0;
q.push(node(s,0));
while(!q.empty()){
int point=q.top().num;
q.pop();
if(vis[point])continue;
vis[point]=true;
for(int i=head[point];i;i=nxt[i]){
int son=to[i];
if(dis[son]>dis[point]+1){
dis[son]=dis[point]+1;
q.push(node(son,dis[son]));
}
}
}
}
全源最短路
即任意两点之间的最短路。
\(Floyed\)
原理
略。
性质
无负环图。
时间复杂度\(O\left(n^{3}\right)\)，空间复杂度\(O\left(n^{2}\right)\)
\(Code:\)
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
\(Johnson\)
（挖坑）
标签：right,int,短路,left,节点,dis From： https://www.cnblogs.com/jd122/p/16953735.html