最短路算法

摘要

复习一下模板

2019.6.4:编入精选文章

图的最短路,指的是在一个加权图 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 是否被访问,全部初始化为未访问;如果被访问,也代表最短路已经求得。

只要有结点未被标记:

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

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

有人问 Bellman-Ford 算法是是啥。其实这是 SPFA 的弱化版反正你知道它大概可以被遗忘就对了

SPFA 算法的思想就是不断更新结点的状态,直到不能更新为止。而 SPFA 把待更新(待松弛)的结点存到队列中。

算法描述

在图 G 中,s 为源结点

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

将源结点入队,并标记 .

当队列非空,即仍有结点需要松弛操作时,做下述操作:

  1. 取出队首为 ,标记 为出队。

  2. 对于结点 p 的所有正向连接结点做松弛操作

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

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

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

模板代码

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

int dis[N];
bool vis[N];
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s), dis[s]=0;
    while(q.size()){
        int u=q.front();
        q.pop(), vis[u]=0;
        for(int i=h[u];i;i=e[i].nex){
            const int &v=e[i].t, &w=e[i].v;
            if(dis[v]<=dis[u]+c)continue;
            dis[v]=dis[u]+c;
            if(!vis[v])q.push(v), vis[v]=1;
        }
    }
}

SLF 与 LLL 优化

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

Small Label First 策略,设要加入的结点是 j,队首元素为 i,若 d[j]<d[i],则将 j 插入队首, 否则插入队尾。

Large Label Last 策略,设队首元素为 i,队列中所有 dist 值的平均值为 x,若 dist[i]>x 则将 i 插入 到队尾,查找下一元素,直到找到某一 i 使得 ,则将 i 出对进行松弛操作。引用网上资料,SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。

所以,SPFA 做为一个不稳定的算法,惨遭各种最短路模板卡,到底有什么用?

SPFA 可以处理带负权边的最短路,相比之下 Dijkstra 就不行,因为带负权的图无法保证每次遍历到的点是已求得最优解。差分约束也常用 SPFA 求解。

最短路与 DP

其实很多人可能会想到,我在取出堆首元素的时侯,其实可以判断该结点能否更新。如果不能更新,就用它更新它的相邻结点;否则就更新,然后重新丢到堆里面,等待下一次被取出。

如何判断能否更新?因为堆的键值就是最短路值,那么我们比较这个键值与 dist 数组就可以判断该结点是否被松弛过,如果未被松弛过就拿他更新别的结点。

这样的复杂度仍是 的。但是你发现它是可以用来处理带负权边的图的!

其实如果把 SPFA 改成用堆维护的话,你发现它 TM 也是这个算法!

两者最终都回归到了堆维护最短路的算法上。这实际上就是一种动态规划,而且带有一点迭代的性质在里面。动态规划通过 1 次或者若干次选择决策更新最优解的方式求解问题,而最短路算法的实质也是不断选择合适的边做为最短路上的边,以此更新当前结点的 DP 值。DP 的边界就是所有的结点都无法更新的时侯,这与迭代的边界类似。下午讲解的 Floyd 算法也是基于 DP 思想的多源最短路算法。

Floyd 算法

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

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

.

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

时间复杂度 .

模板?只有两行 emmm 于是来一道模板题吧

[LG2910] 寻宝之路

给一个图,问顺次经过 的最短路长度。 .

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

~完结撒花~


  转载请注明: Sshwy's Blog 最短路算法

 上一篇
Tarjan 算法之无向图 Tarjan 算法之无向图
Tarjan 要素 DFS 搜索树:即对图进行 DFS 遍历时所有递归到的边组成的树。 时间戳:对于每一个结点,我们用 DFN[i] 表示结点 i 被遍历时的次序。 追溯值:Tarjan 算法引入了追溯值 low[x]. 设以 x 为根的子
2018.12.06
下一篇 
优先队列 | 二插堆 优先队列 | 二插堆
简介二叉堆的逻辑结构是一颗完全二叉树,然而它的实现却是用一维数组实现的。二叉堆分小根堆和大根堆。对于小根堆中的结点 x,其子树的所有结点键值均大于 x,即值越小的越靠近根结点,根结点的优先级最高。(大根堆同理)二叉堆常用于解决一些队列模拟问
2018.11.29
  目录