前言
Standing on the Shoulders of Giants.
此处讨论无向、无重复边、无自环、无权重的图的最短路径算法。
其他诸如有向、自环、节点权重、边权重等相关的算法可基于此算法为基础做延展,此处不作展开讨论。
本文受既往前辈们对图搜索、最短路径等各种算法思想的启发,创造出了一种以构建 “最短路径树” 来查找图中最短路径的算法 ——Shin's Algorithm
。
以下将介绍其算法步骤、伪码、要点等。顺便提供案例部分用以说明按 Shin's Algorithm
进行发现最短路径的计算过程。
图-最短路径
查找图中两个节点、单源节点或顶点对之间最短路径。
概念: 发现源点s
与 目的节点t
之间的最短路径,s!=t
。
在图的广度优先遍历中,提到了一个重要定理:
重要定理:广度优先搜索计算出来的即是最短路径。
有关此定理的证明可参考相关书籍,此处不展开描述,此处讨论的是利用广度优先算法的变种来查找图中的最短路径。
Shin’s 算法
在查找过程中,本算法会构造一棵树,树中的节点个数一般大于等于图中节点个数。算法过程中的树此处称其为“最短路径树”。
算法步骤描述
-
编号
将图中的所有节点进行从0
开始的自然数递增序列编号。 -
图表示
使用编号后节点,将图以邻接矩阵或邻接链表的表示方式表示。 -
构建最短路径树并查找最短路径
遍历编号节点,分别以各编号节点为源点做为树根,以其邻接节点作为树的孩子节点候选集 ——广度优先搜索思想。
对候选节点,做筛选,若孩子节点候选集中的节点已经在其祖先中出现过,则抛弃。否则,可将其作为孩子节点。
重复查找孩子节点,直至所有节点都出现在祖先集合中为止。
在给树添加孩子节点的过程中,同时通过反向查找父辈直至树根路径。此路径经过反转,即为源点至该孩子节点的最短路径。
算法过程
在开始前,先引入此算法中提及树节点数据结构以方便构造“最短路径树(SPT, Shortest-Path Tree)”:
如无特殊说明,本文中的树,即指的是以此数据结构构造的 SPT。
1 | SPT_Node { |
树节点逻辑结构示意如下:
1 | ------------------------- |
SPT 节点逻辑结构应用举例
如有树:
1 | L0 ----------- 0 --------------- L0 |
则其逻辑结构示意为:
1 | SPT Node: |
符号描述
1 | G: 图 G。 |
此处以邻接矩阵方式表示的图来作算法过程描述,以邻接链表方式表示的算法过程类似,此处不赘述。
伪码描述
查找编号 s
的所有最短路径 :
1 | Shortest-Paths search |
判断编号 number
是否在树中祖先节点出现过相同的:
1 | isPredecessor(number, level) |
发现 SPT树根至当前节点最短路径途经节点编号:
1 | findPredecessorPath(Node node) |
Shin’s 算法举例
比如,有图Graph=G(V, E)
如下:
1 | A |
编号后 结构类似:
1 | 0 |
以邻接链表(Adjacency List) 可表示为:
1 | 0 -- 1 -- 2 -- 3 --4 |
以邻接矩阵(Adjacency Matrix) 可表示为:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | |||||||
1 | 1 | 1 | |||||||||
2 | 1 | 1 | |||||||||
3 | 1 | 1 | |||||||||
4 | 1 | 1 | |||||||||
5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||
6 | 1 | 1 | |||||||||
7 | 1 | 1 | |||||||||
8 | 1 | 1 | |||||||||
9 | 1 | 1 | 1 | 1 | |||||||
10 | 1 |
剖析 1:以编号 0
为源点的所有最短路径
以 0
为源点构造的 SPT
示意:
1 | Shortest-Paths Tree's Node Legend: |
以 0
为源点构造的 SPT
的逻辑结构示意:
1 | L0 ----------- 0 --------------- L0 (1 ) \ |
可以看出,此树高 5 层,有 45 个节点。其中编号为 5
, 6
, 7
, 8
, 9
, 10
的节点出现了多次。
因采用了以上 SPT_Node
数据结构,每个节点可以反向找到其父母节点,且其父母节点有且只有一个。故而,可以知道,编号重复的次数即为树根到该节点最短路径条数。
从树高大于 1
的节点个数,即为以树为源点出发的最短路径条数。
故,以 0
为 源点的最短路径一共有 44 条 (—— (45-1), 45个 nodes 减去 1个源点)。
所有路径如下示意:
1 | path-0 : [0, 1] |
通过 SPT 编号节点转化为图中节点,即可得到图的最短路径。
剖析 2:以编号 5
为源点的所有最短路径
以 5
为源点构造的 SPT
的逻辑结构示意:
1 | L0 -------- 5 -------- L0 (1) \ |
可以看出,此树高 3 层,有 18 个节点。其中编号为 0
, 9
, 10
的节点出现了多次。
另外,可以间接反映,编号为 5
的源点 分别到 编号 0
, 9
, 10
的节点之间的最短路径个数,即为 编号 0
, 9
, 10
出现的次数。如 5
到 0
之间有 4 条最短路径;而 5
到 9
,5
到 10
之间分别有 3 条。
类似前述,以 5
为 源点的最短路径一共有 17 条。
所有路径如下示意:
1 | path-0 : [5, 1] |
剖析 3:以编号 9
为源点的所有最短路径
以 9
为源点构造的 SPT
的逻辑结构示意:
1 | L0 ----------- 9 --------------- L0 (1 ) \ |
类似前述,以 9
为 源点的最短路径一共有 31 条。
所有路径如下示意:
1 | path-0 : [9, 6] |
其他节点类似,此处不赘述。
要点
- 此算法以 广度优先搜索 为指导基础,通过编号、构建 “最短路径树”、反转等算法过程,进而查找出图中的最短路径。
- 构造树过程中,始终以图 1 度关系节点(——广度优先 思想)作为当前节点的孩子节点候选集。
- 构造树过程中,孩子节点候选集中剔除当前树节点的父辈集合中出现过的编号相同的节点,剔除后的节点即可作为当前节点的孩子节点。
- 从当前树节点反向查找父辈节点路径,直到根节点为止。反转此路径即为源点至当前树节点路径。
- 相同编号节点只会出现在树的相同层,不会跨层存在。
- 树节点中编号相同的节点个数等于根节点出发到该对应编号图中节点最短路径条数。
- 树中节点个数总和减 1 即为以 根节点 出发,对应编号图中节点的最短路径总条数。
应用
-
查找出图中的 单源最短路径(Single-Source Shortest Paths)、每对顶点间的最短路径(All-Pairs Shortest Paths) 、路径条数 等。
-
对此算法进行一些变动后,在非联通的图中,可通过查找图中最短路径历经数次,来发现图中所有的联通子图。
其它
- 核心指导思想: 广度优先搜索 算法原理及其 最短路径定理。
- 算法名称:
Shin's Algorithm
。与Dijkstra'a Algorithm
,Bellman-Ford
,Floyd-Warshall Algorithm
,Johnson’s Algorithm
等算法名称相比,我愿称其为Shin's Algorithm
~~(^_^)
致谢
由衷的感谢那些在计算机基础学科做出贡献,默默研究的人们!
Standing on the Shoulders of Giants.
参考
[1] Thomars H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms.