最短路教程

单源最短路

给出一个图G,在图中选一个起点S,我们要求出从起点到图上各点的最短路径,这就是单源最短路问题 (Single Source Shortest Path, SSSP)。

问题分析

无环性

  • 最短路是NPC问题,但当保证了图中不存在负环时,化为P问题。
    考虑如果有负环,就可以一直在负环上走,永远也不会到达最短。
  • 最短路是指从起点到终点的路径,可能有多条,也可能不存在(起点和终点不联通?在起点到终点的路径上可能出现负环?)
  • 最长路可以用最短路解决。
    边权取负值,注意不可以有正环。
  • 最短路不可能有环。
    如果有正环,这个正环的一半完全可以不走。
    如果有负环,可以不停在负环上走,永远取不到最短路。

    最短路没有环

传递的最优性

若最短路u \rightarrow  v经过中间点w,则u \rightarrow ww \rightarrow  v的路径分别是uwwv的最短路。

最优性有传递性的一个例子

这是最短路最重要的性质,也是各种主流最短路算法的中心思想。

我们以下面图为例来进行解说,假设0号点为指定的起点:

图中绿色的部分是我们目前已经“确认”了的区域,绿色的边就是我们找出的最短路,其他颜色的点都是我们没有找出最短路的点,我们可以发现在已确认区域内部,上面的传递性当然是成立的。

再考虑图中红色的部分,这些都是从绿色区域可以直接到达的,也就意味着一定存在一条路径,前面若干条边都是绿色的,最后一条边是红色的,而且这条路径是从起点到红色的店的最短路(当然,在确定了这条最短路之后,这个红色的点和红色的边会被设定为绿色,这个点的其他入边会变为灰色)。
这种性质提示我们可以记录从起点到已经确认的点的最短路,也就是说利用动态规划的思想。

同时我们也可以提出下面的两种贪心想法:

  • 如果一个红色的点的所有入边都已经变红,只要选取里面最短的那个红边纳入最短路,就可以得到这个点对应的最短路(最短连最短一定最短)。
  • 如果没有任何一个红点的所有入边都变红,那么我们可以试算每个红点经由红边得到的最短路,挑选里面最短的那个纳入绿色区域(因为这个时候这个点已经不可能取到更短的路径了)。

根据最优性的传递性,这两种贪心的想法都是合理的。主流的最短路算法都是基于动态规划思想和贪心思想的。

最短路树/最短路DAG

为什么单源最短路形成树?

前面提到了最短路的无环性和传递性,假设每个点对应的最短路的解是唯一的,我们可以轻松发现,把所有点的最短路对应边在图上染出来,同所有的点一起正好形成一棵树。

如果考虑多解,就会形成一个DAG。

算法

下面将会介绍几种主流的单源最短路算法及其实现,依然以此图举例:

在开始之前,我们要介绍一个术语“松弛(Relax)”,松弛操作可以表示为:

其中dis是从起点到某个点的距离,len是边的长度,u是一个绿色点,v是一个红色点,prv表示某个点在最短路上的前趋。也就是说松弛操作实际上就是试算红色点最短路的过程。

Bellman-Ford

Bellman-Ford 算法可以概括为:不停进行迭代,每次迭代尝试松弛所有边,迭代最多进行V-1次(V是图的点数),如果一次迭代中没有进行任何成功的松弛,算法可以立即终止,算法复杂度为O(VE)(E是图的边数)。实现如下:

为什么这种算法是合理的呢?联想我们提到的最短路的性质:

  • 所有的最短路形成树,根据树的性质,N个点的树有N-1条边。
  • 基于两个贪心的想法,如果我们每一轮迭代都松弛每个边,每一轮都可以确定一个红点成为旅店,一定至少往最短路树中增加一条边。
  • 这样,我们至多经过N-1次迭代可以得到最短路。

如果图里有负环,会发生什么呢?我们知道经过N-1次迭代就可以确认所有点的最短路了,也就是说第N次迭代将会没有成功的松弛。但是如果有负环,松弛过程将不断尝试在负环中回环,也就是说第N次迭代中将会出现成功松弛。我们可以利用这个特性来判断图中是否有负环。

SPFA

Shortest Path Faster Algorithm实际上是Bellman-Ford的队列实现。我们注意到在上面的迭代实现中,我们每一次都访问了许多绿色边和灰色边,而这些边的松弛操作实际上都是没有用的,如果我们使用队列实现,每一次只松弛红色边,算法的效率就会有所提高。SPFA的代码实现如下:

SPFA的复杂度与Bellman-Ford相同,都是O(VE),然而在实际应用中,SPFA很少会达到这么高时间,在一些情况中,SPFA的效率甚至比Dijkstra高。

Dijkstra

Dijkstra算法适用于所有的边权都为正的图,算法的语言表述如下:

  1. 初始化访问标记数组vis[]为全false,vis[x]表示x是否被访问过
  2. 初始化距离数组dis[]为全INF,dis[起点s]为0,dis[x]表示起点到s的距离
  3. 执行n次下述过程(n为图的点数):
    1. 在所有vis为false的点中挑一个对应的dis值最小的出来(如果有多个就随便选一个),令其为u
    2. 令vis[u]=true
    3. 对于所有u出发的边,进行一次松弛操作

可以发现,在Dijkstra算法中,一个点只要被访问,就会变成绿色点,也就是这个点对应的最短路被确认。联想我们上面提到过的传递性质里面的贪心思想,不难说明这种方法的合理性。假设一个点t在被访问的时候并没有取到最短路,那么必然存在另外一条更短路径能够到达t点,因为我们每一次挑选dis最小的点访问,那么这条更短路径中与t邻接的那个点必然会被先行访问,所以不存在这种不合理的情况。

那么,为什么Dijkstra不适用于带有负权边也可以得到解释,如果没有负权边,最短路径上面的dis值可以保证单调,然而引入负权边之后这种单调性就消失了,我们之前的贪心策略也就不合理了。

Dijkstra的实现难点主要在“挑选已访问点中dis最小的那个”这一步上,这里是Dijkstra性能的瓶颈,这一步通常使用堆结构来实现。C++ STL中自带的优先队列由于无法进行堆内值的变更操作,所以实现出来的复杂度并不稳定(因为部分点会重复入队),而且可能需要使用仿函数技术进行运算符重载,一个如此实现的例子如下:

可以发现在实现的思路上实际上与SPFA并无太大区别,其实我们也可以把SPFA中的普通队列换成优先队列,可以有一定的启发式作用。

要真正地实现Dijkstra,除了自己手写堆之外,还可以考虑使用pd_ds扩展库,p b_ds中提供了可以调整堆内值的优先队列,但是pb_ds并不一定在所有环境中提供,有一定风险。

Gabow

这是一种与前面若干种方法截然不同的最短路算法,使用Scaling Method,这不是本文在当前版本要讨论的内容。

应用

[…待更]

多源最短路

问题概述

在单源最短路的基础上,多源最短路问题要求快速求出图中任意点对之间的最短路。

算法

除了运行N次单源最短路之外,多源最短路问题还有一种实现起来异常简单的Floyd-Warshall算法,其本质是动态规划。

其中dis[i][j]是邻接矩阵,如果i->j邻接,则值为边权,否则为无穷大。在实现过程中,注意三个循环的顺序为kij并非ijk,这是为了利用CPU的缓存优化,尽量不跳行读取,这种优化可以大大提高程序运行效率。

应用

[…待更]

总结

下面这张简单的思维导图大略的列出了最短路相关的部分考点。

最短路相关知识的思维导图

参考

后缀数组

构造后缀数组

倍增前缀法

DC3

 

经典问题

最长公共前缀(LCP)

可重叠最长重复子串

不可重叠最长重复子串

可重叠k次重复最长子串

不相同子串数目

最长回文子串

最长循环节

重复次数最多的循环节

最长公共子串

长度不小于k的公共子串个数

在至少k个字符串中出现的最长子串

每个字符串至少出现两次且不重叠的最长子串

出现或反转后出现在每个字符串中的最长子串

 

 

 

 

 

单模式串匹配问题与KMP算法

单模式串匹配问题

问题定义

给出一个字符串T,称为模式串,再给出一个字符串S,称为原串,问模式串在原串中是否出现,出现位置都有哪些?

举个例子,T = “ha” ,S = “hahaschool” ,T在S中出现了两次,分别是S[0~1]和S[2~3](下标从0开始)。

朴素解法

很简单,只要枚举T在S中出现位置的起点和终点,然后再逐位把S中的字符和T中对应位置的字符比对,如果全部对应,就说明T在S的该段匹配。

优化解法

在暴力匹配中,如果发生了失配(S中的字符不等于T中对应位置的字符),那么我们将会放弃当前的匹配进度,直接从S的下一位开始匹配。如果我们可以保留一部分的匹配进度,就可以减少计算量。这种想法就是我们接下来要讲的KMP算法的源头。

KMP算法

求Next数组

 

使用Next数组加速字符串匹配

 

Next数组的其他应用

最长循环节

结合动态规划

Extended KMP

最长回文子串和Manacher算法

最长回文子串

问题定义

给出一个字符串,找出其中的最长回文子串。

“回文串”是指,这个字符串从前往后读,和从后往前读效果是一样的。

比如”testset”、”hahaschooloohcsahah”,这样的串都是回文串。

子串是指在字符串中抽出的一段连续的字符,比如”school”是”hahaschool”的一个子串,”hsol”并不是”hahaschool”的子串,因为在原串中的对应位置不连续,”poi”也不是”hahaschool”的子串,因为无法在原始串中无法找到’p’和’i’。

朴素解法

解法一

枚举最长的回文串的长度len,在原始串中枚举len长度的子串,然后判断该子串是否为回文串,如果是的话更新答案。

时间代价:枚举长度O(n) * 枚举子串O(n) * 判断回文O(n) –> O(n^3)

解法二

枚举最长回文子串的中心center,然后尝试扩张以center为中心的回文子串(检查两边的字符是否相等,是的话扩张,否则停止)到最大,然后更新答案。

时间代价:枚举中心O(2n)=O(n) * 扩张O(n) –> O(n^2)

优化解法

解法三

分奇偶二分最长回文子串长度len。

检查len是否可行的方法是:然后枚举len长度的回文串的中心位置,然后判断是否回文。

时间代价:二分答案O(2logn)=O(logn) * 检查可行性O(n) * 回文判断O(n) –> O(n^2 logn)

看起来比解法二还慢,我们可以再加一个优化:利用Rabin-Karp方法哈希原始串和原始串反向串,通过判断回文串的左半部分的哈希值是否等于反向的右半部分哈希值,就可以判断是否回文,这样就可以实现回文判断的O(1)。

时间代价: 二分答案O(2logn)=O(logn) * 检查可行性O(n) * 回文判断O(1) –> O(n logn)

解法四

首先,回文子串的左半部分是原始串的一个后缀,右半部分是原始串的反向串的一个后缀。

使用后缀数组,首先把原始串和原始串的反向串中间用一个特殊字符(只要字符串中没有出现过就可以,比如’#’)链接,然后求出链接后的串的后缀数组和LCP数组(height)。

接下来,只要枚举回文串的中心center,然后在利用LCP数组查询center对应的原始串后缀和反串后缀的LCP即可。

时间代价:后缀数组O(nlogn)或O(n) + 枚举中心O(n) * 求LCP O(logn) –> O(nlogn)

解法五

就是我们接下来要讨论的Manacher算法,可以达到O(n)的时间复杂度下界。

Manacher算法

开始之前的一些定义

  • 我们的数组下标都是从0开始
  • 我们接下来将称呼原始串为T
  • 我们知道,回文子串的中心位置可能是一个字符本身,也可能是两个字符之间的空隙,所以我们接下来将把T做一些改动,即在每个字母的前后插入一个特殊字符’|’来表示字符间的空隙,如”abababa”,将会变成”|a|b|a|b|a|b|a|”,我们令这个改动后的串为S。简单观察一下,我们就可以发现,S的长度len(S) = len(T) * 2。
    manacher0
  • 我们定义数组rad[],rad[center]表示以center为中心的回文串的回文半径,其中center对应S的下标。举个例子,”|a|b|a|b|a|”,rad[0] = 0(分割线暂时忽略),rad[1] = 1(“a”构成回文),rad[5] = 5(“a|b|a|b|a”构成回文)。

为了更好地理解上述定义,再附两个例子:

lps13

lps12

我们接下来的目标就是在线性时间内算出rad[]的值。

先来找找规律

先来看一个例子:”abaaba”

Manacher3

观察图中标示出来的回文子串,发现什么了?

  • rad[2] = rad[4] = 0
  • rad[1] = rad[5] = 1

如果我们知道了rad[1]、rad[2]、rad[3]的值,那么我们就不用再去算rad[4]和rad[5]了,因为它们等于子串中心3左边的对应的点的rad值。

然后再观察以6为中心的回文子串,你会发现:

  • rad[5] = rad[7]
  • rad[4] = rad[8]

也就是说如果我们已经知道了rad[1~6]的值,rad[7~11]的值就不用额外算了,他们都可以对应到以6为中心的回文串的左半部分。

那我们再来看一个例子:”abababa”

Manacher4

按照上个例子那样,注意图中的标示,我们发现rad[1~6]可以和rad[8~13]对应上。

看起来在回文串的中心两边的rad值是对称的。然而这一点并不是一直成立
。我们注意当前这个例子的位置3和位置11,我们发现这两个位置对应的回文串内部并没有刚才那样的对称关系。

这给了我们一个提示,也许有没有这种对称关系取决于某种条件,当这种条件满足的时候,就可以通过对称关系来减少计算量,从而达到线性时间复杂度。如果条件不满足的话,就需要暴力判断。

那么我们接下来的目标就是探索这个规律。

在深入问题之前的补充定义

在深入问题之前,需要补充一些新的定义:
manacher5

  • 中心位置centerPos:在中心位置的rad已经算好,我们令rad[centerPos]为d
  • 右边界centerR:在中心位置右侧距离中心位置d单位远的位置,即中心位置所示的回文串的右边界,centerR = centerPos + d
  • 左边界centerL:在中心位置左侧距离中心位置d单位远的位置,即中心位置所示的回文串的右边界,centerR = centerPos – d
  • 当前处理位置curR:在中心位置右边,我们需要求rad值的位置
  • 当前参考位置curL:在中心位置左边,我们已经求好了rad值的位置
  • 我们发现有这样的几个等式:
    • centerPos – curL = curR – centerPos
    • centerL = 2*centerPos – curR
  • i-左回文串:中心距离centerPos i单位远的左侧的回文串,即以curL为中心的回文串
  • i-右回文串:中心距离centerPos i单位远的右侧的回文串,即以curR为中心的回文串
  • 中心回文串:中心位置对应的回文串

深入问题

当我们处在中心位置centerPos的时候,我们之前已经求出了centerPos及之前所有位置的rad值了,这也意味着centerPos-d到centerPos+d是一个回文串。我们现在要处理curR位置,即算出rad[curR]。

我们需要一点分类讨论,首先是:

情形1:

i-左字符串被真包含(没有碰到中央回文串边界)于中心回文串内,且i-左字符串不是中心回文串的后缀,则有rad[curR] = rad[curL],即:

我们来考虑”abababa”这个例子:
manacher6

我们现在已经算出了rad[0~7],中心位置 centerPos = 7,对应回文串半径 rad[centerPos] = d = 7,左边界 centerL = 0, 右边界 centerR = 14。接下来我们要去算8及之后的rad值。

对于curR = 8,有curL = 6,和rad[curL] = 0,同时有 centerR – curR = 14 – 8 = 6,这符合情形1,所以我们有rad[curR] = rad[curL] = 0。

接下来对于curR = 10和curR = 12,也适用情形1。它们分别有:

  • rad[10] = rad[4] = 0
  • rad[1] = rad[2] = 0

然后,我们来看位置9,我们有:curR = 9, curL = 5,centerR – curR = 5。

这里我们有rad[curL] = centerR – curR,也就是说情形1并不适用。我们同时注意到了centerR是整个字符串的末尾,这也就意味着中心回文串是输入的字符串的后缀。也就是:

情形2:

当i-左回文串是中心回文串的前缀且中心回文串是输入字符串的后缀时,rad[curR] = rad[curL]。即:

位置9、11、13、14都适用情形2,我们有:

  • rad[0] = rad[5] = 5
  • rad[11] = rad[3] = 3
  • rad[13] = rad[1] = 1
  • rad[14] = rad[0] = 0

情形1和情形2的原理其实就是利用了回文串的性质,当一个较小的回文串被包含在一个较大的回文串中,且小回文串的中心在大回文串的左半部分时,根据回文串的对称性,大回文串应该有和左半部分相同的另外一个小回文串,中心在右半部分。

在情形1中,右边的回文串一定等于左边的回文串,否则如果右边的回文串能够扩张,左边的回文串也必然能够扩张,因为左边的回文串被真包含于大回文串之内(没有碰到大回文串边界),扩张时新加的字母也一定出现在了大回文串的右侧,扩张了右边的回文串,所以左边等于右边,反之亦然。

在情形2中,虽然左边的回文串是大回文串的前缀,如果右边发生扩张,不能保证对应的字母出现在左边,然而根据我们的条件,右边正好是整个输入字符的后缀,也就是右边的回文串根本不可能延长,所以左边等于右边。

上述的两种情形我们可以直接得出rad[curR]的值,不需要别的计算。

此外,还有两种情形:

情形3:

当i-左回文串是中心回文串的前缀且中心回文串不是输入字符串的后缀时,rad[curR] >= rad[curL]。即:

情形3基于情形2,情形2的右边回文串是不能加字符扩张的,而情形3可以。当右边的回文串加字符扩张后,左边的回文串并不能扩张,因为新加的字符在中心回文串的外面,这个字符没有对应到左边去。

情形3只是给rad[curR]提供了一个下界,接下来我们需要暴力检验才能得到真实的rad[curR],不过这依然减少了运算量。

情形4:

当i-左回文串与中心回文串交叉时,rad[curR] >= centerR – curR。即:

 

当我们的中心回文串不能覆盖左边回文串的时候,我们不妨缩小左边回文串到中心回文串能覆盖的程度,这样一来就和情形3是一样的了。

经过了以上四种情形的分类讨论,我们覆盖了所有在处理rad[curR]中可能出现的情况。

接下来我们基于这种思路来做实现。

实现

这份实现严格遵守了上面的思路,但是比较复杂,不太适合在实战中使用。

 

简化实现

观察一下我们分析的4种情形,我们会发现其实没有必要写那么繁琐,我们可以从下面几个方面减轻代码负担:

  • 我们没必要计算S数组对应于T数组的位置,直接把S数组当作目标即可。
  • 前3种情形都是令rad[curR] = rad[curL],第四种情形是令rad[curR] = centerR – curR,我们不妨直接令rad[curR] = min(rad[curL], centerR – curR)。
  • 对于情形1,2,不需要扩张,但我们尝试扩张也没什么关系。

这样,我们可以把上面的一大堆缩减到这样的程度:

 

不刻意压行就可以达到简短的20行代码,非常简洁好记。

应用举例

裸题

左端点对应最长回文串

结合线段树

参考文献与致谢

  • Anurag Singh from GeeksforGeeks for pictures and some ideas.
  • doubility::Zhenkun Csi for beautiful implementation in C++.
Scroll to top