最短路算法·ShortestPath

摘要

复习一下模板

前言

最短路,即在一个加权图G中某两点相距的最短路程的长度(有时要求记录路径)。

单源与多源最短路

计算最短路,通常不会只求某两点的最短路,而会将许多点对间的最短路一起算出来。这具体表现在:

  • 单源最短路:计算图G中某一点s到其他的所有点的最短路
  • 多源最短路:计算图G中任意两点的最短路

至于为什么会计算出其他点的最短路,下文将揭晓

松弛操作

最短路算法,都会运用到松弛操作,字面义就是,将两点间原本的较长的最短路进行更新替换,松弛为较短的路径
也就是说,将当前存储的最短路长度进行更新,在算出其他点对间的目前最短路长度后,利用这个已知数据去更新与它直接连接到的结点直到不能更新为止,此时的“目前最短路”即为最终要求的最短路。

松弛操作的基本模式是这样的:

  • 对于两点u,w的目前最短路,利用u,v的目前最短路,v,w的目前最短路去更新u,v的最短路,即
  • 单源最短路程序实现中,若已求得图G中两结点u,v的目前最短路为s(u,v),则对于v所直接连接到的结点w:
    至于为什么这么实现,原因在于单源——毕竟只关心u到其他点的最短路,那么v到w的最短路就极不容易求,因此替换为两点的直接距离,减小复杂度。

这就是为什么会计算出其他点的最短路的原因——为了松弛操作的更新。

注意事项

  • 图G既可能是有向图,也有可能是无向图(可把无向图理解为双向连边切权值相等的有向图);既可有环也可无环
  • 勿把u到v的最短路v到u的最短路混为一谈,因为边是有向的,不一定能反着走
  • 对于点对间的最短路长度的初始化,绝大多数情况会初始化为一个很大很大的数,方便更新
  • 对于最短路的路径问题,通常是记录前一个结点的编号,即,在更新最短路长度的同时,更新结点编号

Dijkstra算法

单源最短路算法,时间复杂度 ,利用二叉堆可优化到

算法描述

在图G中,s为源节点。
定义d[i]为结点s到结点i的最短路,将d[i]初始化为很大的数,d[s]初始化为0(源点本身)。
定义w(u,v)为u到v直接连接的边的权值(保证u到v有直接连接的边,有方向性)。
定义v[i]记录结点i是否被访问,全部初始化为未访问;如果被访问,也代表最短路已经求得。
则:

  • 找到目前还未被访问的d[i]中的最小值d[p],这是求出的s到p的最终的最短路。将p标记为已访问。
  • 利用这个信息,对于与p连接的所有结点q,进行s到q的松弛操作:d[q]=min(d[q],d[p]+w(p,q))
  • 重复上两个步骤,直到所有结点都被访问。

以结点1为源点。
dijkstra_glf.gif

第一次,发现d[1]==0为最小值,于是标记结点1为已访问,对2,3,5进行松弛操作:
第二次,发现d[2]==4为最小值,于是标记结点2为已访问,对1,3进行松弛操作:
第三次,发现d[3]==5为最小值,于是标记结点3为已访问,对1,2,4进行松弛操作:
第四次,发现d[5]==6为最小值,于是标记结点5为已访问,对1,4,6进行松弛操作:
第五次,发现d[4]==7为最小值,于是标记结点4为已访问,对3,5,7,8进行松弛操作:
第六次,发现d[8]==13为最小值,于是标记结点8为已访问,对4,7进行松弛操作:
第七次,发现d[6]==14为最小值,于是标记结点6为已访问,对5,7进行松弛操作:
第八次,发现d[7]==15为最小值,于是标记结点7为已访问,对4,6,8进行松弛操作:

一点注解

至于为什么,每次要标记最小的结点,是因为:

  • 你会发现,每次取到的最小值按序排列,是逐渐递增的(如例图中第1至8次找出的0,4,5,6,7,13,14,15),换句话说,每次算出的目前最短路长度,是逐渐变长的。
  • 再者,每次你计算的最小值,其实都是之前松弛操作更新后的结点(有红色数字的结点),不会遇到被初始化为INF的结点,因为每一次对该结点的遍历都会更新它所有相邻结点的目前最短路,为下一个最小结点做准备。
  • 第三,假设所有被访问过的结点都求得最小值,用数学归纳法,则下一个最小结点,已经被与之相邻的已访问的结点松弛过;而未被访问的结点的值都大于等于这个结点,说明不可能从未被访问的结点松弛到这个结点;因此这个被与之相邻的已访问的结点松弛过的最小结点的d[],即为它最终的最短路的长度。从而,一步一步,算出全图的单源最短路。

Dijkstra-堆优化

  • 上述算法的复杂度为 ,遇到较大的数据将超时。在寻找每次的最小值时,可使用二叉堆优化。
  • 复杂度降到 .

模板

const int N=1e5+5,M=2e5+5;
struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
int dist[N];
void dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
dist[s]=0,q.push(make_pair(0,s));
while(q.size()){
pii u=q.top();q.pop();
if(dist[u.second]<u.first)continue;
for(int i=h[u.second];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
if(dist[v]<=dist[u.second]+w)continue;
dist[v]=dist[u.second]+w;
q.push(make_pair(dist[v],v));
}
}
}

SPFA算法

SPFA算法是Bellman-Ford算法的优化,全称为Shortest Path Faster Algorithm.

算法描述

在图G中,s为源结点

定义队列que记录还需要进行松弛操作的结点; 记录结点i是否在队列中。

将源结点入队,并标记 .

当队列非空,即仍有结点需要松弛操作时,取出队首为 ,标记 为出队。

  • 对于结点p的所有正向连接结点做松弛操作
  • 如果成功松弛(即 时)
    • 此时q结点的最短路被更新,则从q连出的所有最短路也应当更新。
    • 所以如果q已在队列中,就不用入队;否则,将q入队,标记 为入队

队列空了,说明没有结点需要松弛,算法结束。

时间复杂度O(kE).E表示边数,k为不定系数,通常为2-3.

SLF与LLL优化

上述SPFA算法插入队列的决策是直接插入队尾,这样的时间复杂度仍有冗余。

  • SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若d[j]<d[i],则将j插入队首, 否则插入队尾。
  • LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist[i]>x则将i插入 到队尾,查找下一元素,直到找到某一i使得dist[i]<=x,则将i出对进行松弛操作。

引用网上资料,SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。

Floyd算法

Floyd用于求多源最短路径,即每两点的最短距离。

Floyd基于动规,定义 表示从结点i到结点j,经过(不包括起点终点)前k个结点的最短路

.

实际中可以把第一维直接压掉

时间复杂度 .

[USACO08OPEN]寻宝之路

#include<iostream>
#include<cstdio>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int n,m,sum,a[10002],d[102][102];
int main(){
cin>>n>>m;
FOR(i,1,m)cin>>a[i];
FOR(i,1,n)FOR(j,1,n)cin>>d[i][j];
a[0]=1,a[m+1]=n;
FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)//floyd
if(d[i][j]>d[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];
FOR(i,0,m)sum+=d[a[i]][a[i+1]];
cout<<sum;
return 0;
}