图-最短路径(Shortest Paths)

技术►算法 , , , , ,

前言

Standing on the Shoulders of Giants.

此处讨论无向、无重复边、无自环、无权重的图的最短路径算法。

其他诸如有向、自环、节点权重、边权重等相关的算法可基于此算法为基础做延展，此处不作展开讨论。

本文受既往前辈们对图搜索、最短路径等各种算法思想的启发，创造出了一种以构建 “最短路径树” 来查找图中最短路径的算法 ——Shin's Algorithm。

以下将介绍其算法步骤、伪码、要点等。顺便提供案例部分用以说明按 Shin's Algorithm 进行发现最短路径的计算过程。

图-最短路径

查找图中两个节点、单源节点或顶点对之间最短路径。

概念: 发现源点s 与 目的节点t 之间的最短路径，s!=t。

在图的广度优先遍历中，提到了一个重要定理：

重要定理：广度优先搜索计算出来的即是最短路径。

有关此定理的证明可参考相关书籍，此处不展开描述，此处讨论的是利用广度优先算法的变种来查找图中的最短路径。

Shin’s 算法

在查找过程中，本算法会构造一棵树，树中的节点个数一般大于等于图中节点个数。算法过程中的树此处称其为“最短路径树”。

算法步骤描述

  1. 编号
    将图中的所有节点进行从 0 开始的自然数递增序列编号。

  2. 图表示
    使用编号后节点，将图以邻接矩阵或邻接链表的表示方式表示。

  3. 构建最短路径树并查找最短路径
    遍历编号节点，分别以各编号节点为源点做为树根，以其邻接节点作为树的孩子节点候选集 ——广度优先搜索思想。

对候选节点，做筛选，若孩子节点候选集中的节点已经在其祖先中出现过，则抛弃。否则，可将其作为孩子节点。

重复查找孩子节点，直至所有节点都出现在祖先集合中为止。

在给树添加孩子节点的过程中，同时通过反向查找父辈直至树根路径。此路径经过反转，即为源点至该孩子节点的最短路径。

算法过程

在开始前，先引入此算法中提及树节点数据结构以方便构造“最短路径树(SPT, Shortest-Path Tree)”：

如无特殊说明，本文中的树，即指的是以此数据结构构造的 SPT。

1
2
3
4
5
SPT_Node {
  int number; // 节点编号
  int level;  // 节点在树中的层级
  Node prev;  // 当前节点的父母节点
}

树节点逻辑结构示意如下：

1
2
3
-------------------------
| prev | number | level |
-------------------------

SPT 节点逻辑结构应用举例

如有树：

1
2
3
4
5
L0 -----------    0    --------------- L0
                /   \
L1 ---------   1     2   ------------- L1
              / \    |
L2 -------   3   4   5   ------------- L2

则其逻辑结构示意为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
SPT Node:

Node Address           Node Structure
 /--^--\      /--------------^--------------\
              -------------------------------
&{number}  :  | {prev} | {number} | {level} |
              -------------------------------

---

SPT:

                              --------------------
                         &0:  | null |  0  |  0  |
                              --------------------
                             /^              ^\
                           /                    \
                         /                        \
                       /                            \
                  ---/----------                    --\-----------
             &1:  | &0 | 1 | 1 |               &2:  | &0 | 2 | 1 |
                  --------------                    --------------
                 /^   ^\                              |
               /         \                            |
             /             \                          |
           /                 \                        |  
      ---/----------         --\-----------         --|-----------
 &3:  | &1 | 3 | 2 |    &4:  | &1 | 4 | 2 |    &5:  | &2 | 5 | 2 |
      --------------         --------------         --------------

符号描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
G: 图 G。
G.SN: 经过节点编号后的图。将图中的节点进行从 `0` 开始的自然数递增序列编号，用编号代表图中节点。
G.Adj: 以邻接矩阵 (Adjacency Matrix) 表示的图 `G`。
G.Adj[e]: 以邻接矩阵 (Adjacency Matrix) 表示的*起点*为 `e` 的所有*目的*邻接节点。

Q: 队列。
Q.poll: 获取队列头元素，并从队列头中移除此元素。
Q.offer(e): 将元素 `e` 加入队列尾部。

LEVEL_SPT_NODE_NUMBER: 节点编号为 `number` 、层级为 `level` 的元素集合。
LEVEL_SPT_NODE_NUMBER.add(number, level):  把节点编号为 `number`，层级 为 `level` 的元素添加至 LEVEL_SPT_NODE_NUMBER 集合中。
LEVEL_SPT_NODE_NUMBER.search(level): 查找 层级是 `level` 的所有节点编号。
LEVEL_SPT_NODE_NUMBER.search(number, level):  查找 节点编号为 `number`，层级 为 `level` 的元素在 LEVEL_SPT_NODE_NUMBER 集合中。

List: 有序集合。
List.add(e): 将元素 `e` 添加至 有序集合。
List.reverse: 将有序集合中的所有元素顺序反转。

此处以邻接矩阵方式表示的图来作算法过程描述，以邻接链表方式表示的算法过程类似，此处不赘述。

伪码描述

查找编号 s 的所有最短路径 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Shortest-Paths search

ShinSP(G.SN.Adj, s)

#1     Q={}                             // 初始化，创建一个空的队列 Q
#2     root <- Node(s, 0, null)         // 初始化，将编号为 s 的节点作为树根，其 prev 为 null，level 为 0
#3     Q.offer(root)
#4     LEVEL_SPT_NODE_NUMBER.add(s, 0)  // 将源节点编号、层级加入记录集合
#5     while Q is not empty
#6         u <- Q.poll()                // 取队头，赋于 u
#7         for each v in G.SN.Adj[u.number]              // 遍历 u 的邻接节点，所有的节点均为候选节点，只有符合条件的方可做为对应树的孩子节点
#8             if isPredecessor(v, u.level) is true      // 若编号 v 与 当前 SPT 中的所有节点具有相同 Node 编号
#9                 then continue;                        // 则剔除，继续筛选
#10            else 
#11                child <- Node(v, u.level+1, u)            // 将编号 v 封装为树节点，并复制给 child，做为 u 的孩子节点 —— child.prev 是 u
#12                Q.offer(child)                            // 将选中的孩子节点加入树中
#13                LEVEL_SPT_NODE_NUMBER.add(v, u.level+1)   // 加入记录节点、层级元素的集合
#14                findPredecessorPath(child)     // 发现树根至当前树节点最短路径途经节点编号，此编号通过转化为图中节点，即可得到图 G 的 最短路径。

判断编号 number 是否在树中祖先节点出现过相同的：

1
2
3
4
5
6
7
8
9
10
isPredecessor(number, level)

#1    prev_level <- level       // 给父辈节点层级 prev_level 赋值
#2    while prev_level >= 0
#3        if number IN  LEVEL_SPT_NODE_NUMBER.search(prev_level) // 如果 number 出现在 prev_level 层集合中
#4            then return true
#5        else 
#6            continue;
#7        prev_level--;
#8    return false;

发现 SPT树根至当前节点最短路径途经节点编号：

1
2
3
4
5
6
7
8
findPredecessorPath(Node node)

#1    List.add(node.number)       // 将当前树节点编号加入到 有序集合中
#2    prev <- node.prev;          // 将当前树节点的父辈节点赋于 prev
#3    while prev != null          // 父辈节点不为 null
#4        List.add(prev.number)   // 将父辈节点编号加入到 有序集合中
#5        prev <- prev.prev       // 将父辈节点 prev 重新赋值为父辈的父辈
#6    return  List.reverse        // 反转有序集合 ——最短路径途经节点编号

Shin’s 算法举例

比如，有图Graph=G(V, E)如下：

1
2
3
4
5
6
7
8
9
10
11
    A
 / / \ \
B C   D E
 \ \ / /
    F
  / | \
 G  H  I
  \ | /
    J
    |
    K

编号后 结构类似：

1
2
3
4
5
6
7
8
9
10
11
    0
 / / \ \
1 2   3 4
 \ \ / /
    5
  / | \
 6  7  8
  \ | /
    9
    |
    10

以邻接链表(Adjacency List) 可表示为：

1
2
3
4
5
6
7
8
9
10
11
 0 -- 1 -- 2 -- 3 --4
 1 -- 0 -- 5
 2 -- 0 -- 5
 3 -- 0 -- 5
 4 -- 0 -- 5
 5 -- 6 -- 7 -- 8
 6 -- 5 -- 9
 7 -- 5 -- 9
 8 -- 5 -- 9
 9 -- 6 -- 7 -- 8 -- 10
10 -- 9

以邻接矩阵(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
Shortest-Paths Tree's Node Legend:

  format: 
      {times}: {node number}-{node address} {prev={prev node number}-{prev node address}, number={node number}, level={node level}}

  e.g.:  `5: 5-25272628385  {prev=1-25272846675, number= 5, level=2}`

    times  node number  -  node address       prev node number  -  prev node address        node number    node level
                |               |                  |                    |                        |              |
      5   :     5       -  25272628385  {prev=     1            -  25272846675        , number=  5    , level=  2     }


---
Shortest-Paths Tree's Nodes:

           0:  0-25272844041  {prev=null, number=0, level=0}

           1:  1-25272846675  {prev=0-25272844041, number= 1, level=1}
           2:  2-25272847860  {prev=0-25272844041, number= 2, level=1}
           3:  3-25272847886  {prev=0-25272844041, number= 3, level=1}
           4:  4-25272847912  {prev=0-25272844041, number= 4, level=1}

   --->    5:  5-25272628385  {prev=1-25272846675, number= 5, level=2}
   |
-- | ->    6:  5-25272407974  {prev=2-25272847860, number= 5, level=2}
|  |
|  |       7:  5-25272408126  {prev=3-25272847886, number= 5, level=2}   <---
|  |                                                                        |
| prev     8:  5-25272408279  {prev=4-25272847912, number= 5, level=2}   <- | --
|  |                                                                        |  |
|  |  /    9:  6-25272408479  {prev=5-25272628385, number= 6, level=3}      |  |
|  --<    10:  7-25272408543  {prev=5-25272628385, number= 7, level=3}    prev |
prev  \   11:  8-25272408585  {prev=5-25272628385, number= 8, level=3}      |  |
|                                                                           |  |
|     /   12:  6-25272408800  {prev=5-25272407974, number= 6, level=3}      |  |
-----<    13:  7-25272408838  {prev=5-25272407974, number= 7, level=3}      |  |
      \   14:  8-25272408876  {prev=5-25272407974, number= 8, level=3}      |  |
                                                                            |  |
          15:  6-25272409077  {prev=5-25272408126, number= 6, level=3}   \  |  |
          16:  7-25272409115  {prev=5-25272408126, number= 7, level=3}    >--  |
          17:  8-25272409166  {prev=5-25272408126, number= 8, level=3}   /    prev
                                                                               |
          18:  6-25272409367  {prev=5-25272408279, number= 6, level=3}   \     |
          19:  7-25272409405  {prev=5-25272408279, number= 7, level=3}    >-----
          20:  8-25272409443  {prev=5-25272408279, number= 8, level=3}   /

          21:  9-25272409621  {prev=6-25272408479, number= 9, level=4}
          22:  9-25272409826  {prev=7-25272408543, number= 9, level=4}
          23:  9-25272410005  {prev=8-25272408585, number= 9, level=4}
          24:  9-25272410203  {prev=6-25272408800, number= 9, level=4}
          25:  9-25272410382  {prev=7-25272408838, number= 9, level=4}
          26:  9-25272410561  {prev=8-25272408876, number= 9, level=4}
          27:  9-25272410740  {prev=6-25272409077, number= 9, level=4}
          28:  9-25272410919  {prev=7-25272409115, number= 9, level=4}
          29:  9-25272411098  {prev=8-25272409166, number= 9, level=4}
          30:  9-25272411277  {prev=6-25272409367, number= 9, level=4}
          31:  9-25272411456  {prev=7-25272409405, number= 9, level=4}
          32:  9-25272411635  {prev=8-25272409443, number= 9, level=4}

          33: 10-25272411841  {prev=9-25272409621, number=10, level=5}
          34: 10-25272412074  {prev=9-25272409826, number=10, level=5}
          35: 10-25272412308  {prev=9-25272410005, number=10, level=5}
          36: 10-25272412515  {prev=9-25272410203, number=10, level=5}
          37: 10-25272412722  {prev=9-25272410382, number=10, level=5}
          38: 10-25272412929  {prev=9-25272410561, number=10, level=5}
          39: 10-25272413136  {prev=9-25272410740, number=10, level=5}
          40: 10-25272413343  {prev=9-25272410919, number=10, level=5}
          41: 10-25272413550  {prev=9-25272411098, number=10, level=5}
          42: 10-25272413757  {prev=9-25272411277, number=10, level=5}
          43: 10-25272413964  {prev=9-25272411456, number=10, level=5}
          44: 10-25272414171  {prev=9-25272411635, number=10, level=5}

以 0 为源点构造的 SPT 的逻辑结构示意：

1
2
3
4
5
6
7
8
9
10
11
L0 -----------                0                --------------- L0 (1 )  \
                /         /       \         \                            |
L1 ---------   1         2         3         4   ------------- L1 (4 )   |
               |         |         |         |                           |
L2 -------     5         5         5         5     ----------- L2 (4 )    \
            /  |  \   /  |  \   /  |  \   /  |  \                          > 45 nodes
L3 ------   6  7  8   6  7  8   6  7  8   6  7  8   ---------- L3 (12 )   /
            |  |  |   |  |  |   |  |  |   |  |  |                        |
L4 ------   9  9  9   9  9  9   9  9  9   9  9  9   ---------- L4 (12 )  |
            |  |  |   |  |  |   |  |  |   |  |  |                        |
L5 ------   10 10 10  10 10 10  10 10 10  10 10 10  ---------- L5 (12 ) /

可以看出，此树高 5 层，有 45 个节点。其中编号为 5, 6, 7, 8, 9, 10 的节点出现了多次。

因采用了以上 SPT_Node 数据结构，每个节点可以反向找到其父母节点，且其父母节点有且只有一个。故而，可以知道，编号重复的次数即为树根到该节点最短路径条数。
从树高大于 1 的节点个数，即为以树为源点出发的最短路径条数。

故，以 0 为 源点的最短路径一共有 44 条 （—— (45-1), 45个 nodes 减去 1个源点）。

所有路径如下示意：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
path-0 : [0, 1]
path-1 : [0, 2]
path-2 : [0, 3]
path-3 : [0, 4]
path-4 : [0, 1, 5]
path-5 : [0, 2, 5]
path-6 : [0, 3, 5]
path-7 : [0, 4, 5]
path-8 : [0, 1, 5, 6]
path-9 : [0, 1, 5, 7]
path-10: [0, 1, 5, 8]
path-11: [0, 2, 5, 6]
path-12: [0, 2, 5, 7]
path-13: [0, 2, 5, 8]
path-14: [0, 3, 5, 6]
path-15: [0, 3, 5, 7]
path-16: [0, 3, 5, 8]
path-17: [0, 4, 5, 6]
path-18: [0, 4, 5, 7]
path-19: [0, 4, 5, 8]
path-20: [0, 1, 5, 6, 9]
path-21: [0, 1, 5, 7, 9]
path-22: [0, 1, 5, 8, 9]
path-23: [0, 2, 5, 6, 9]
path-24: [0, 2, 5, 7, 9]
path-25: [0, 2, 5, 8, 9]
path-26: [0, 3, 5, 6, 9]
path-27: [0, 3, 5, 7, 9]
path-28: [0, 3, 5, 8, 9]
path-29: [0, 4, 5, 6, 9]
path-30: [0, 4, 5, 7, 9]
path-31: [0, 4, 5, 8, 9]
path-32: [0, 1, 5, 6, 9, 10]
path-33: [0, 1, 5, 7, 9, 10]
path-34: [0, 1, 5, 8, 9, 10]
path-35: [0, 2, 5, 6, 9, 10]
path-36: [0, 2, 5, 7, 9, 10]
path-37: [0, 2, 5, 8, 9, 10]
path-38: [0, 3, 5, 6, 9, 10]
path-39: [0, 3, 5, 7, 9, 10]
path-40: [0, 3, 5, 8, 9, 10]
path-41: [0, 4, 5, 6, 9, 10]
path-42: [0, 4, 5, 7, 9, 10]
path-43: [0, 4, 5, 8, 9, 10]

通过 SPT 编号节点转化为图中节点，即可得到图的最短路径。

剖析 2：以编号 5 为源点的所有最短路径

以 5 为源点构造的 SPT 的逻辑结构示意：

1
2
3
4
5
6
7
L0 --------          5          -------- L0 (1) \
             /  /  / | \  \  \                   |
L1 ------   1  2  3  4  6  7  8   ------ L1 (7)   \
            |  |  |  |  |  |  |                    > 18 nodes
L2 ------   0  0  0  0  9  9  9   ------ L2 (7)   /
                        |  |  |                  |
L3 ------------------   10 10 10  ------ L3 (3) /

可以看出，此树高 3 层，有 18 个节点。其中编号为 0, 9, 10 的节点出现了多次。

另外，可以间接反映，编号为 5 的源点 分别到 编号 0, 9, 10 的节点之间的最短路径个数，即为 编号 0, 9, 10 出现的次数。如 5 到 0 之间有 4 条最短路径；而 5 到 9，5 到 10 之间分别有 3 条。

类似前述，以 5 为 源点的最短路径一共有 17 条。
所有路径如下示意：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
path-0 :  [5, 1]
path-1 :  [5, 2]
path-2 :  [5, 3]
path-3 :  [5, 4]
path-4 :  [5, 6]
path-5 :  [5, 7]
path-6 :  [5, 8]
path-7 :  [5, 1, 0]
path-8 :  [5, 2, 0]
path-9 :  [5, 3, 0]
path-10 : [5, 4, 0]
path-11 : [5, 6, 9]
path-12 : [5, 7, 9]
path-13 : [5, 8, 9]
path-14 : [5, 6, 9, 10]
path-15 : [5, 7, 9, 10]
path-16 : [5, 8, 9, 10]

剖析 3：以编号 9 为源点的所有最短路径

以 9 为源点构造的 SPT 的逻辑结构示意：

1
2
3
4
5
6
7
8
9
L0 -----------                 9                 --------------- L0 (1 )  \
                /          /        \         \                            |
L1 ---------   6          7          8         10   ------------ L1 (4 )   |
               |          |          |                                      \
L2 -------     5          5          5     --------------------- L2 (3 )     > 32 nodes
            / / \ \    / / \ \    / / \ \                                   /
L3 -----   1 2   3 4  1 2   3 4  1 2   3 4   ------------------- L3 (12 )  |
           | |   | |  | |   | |  | |   | |                                 |
L4 -----   0 0   0 0  0 0   0 0  0 0   0 0   ------------------- L4 (12 ) /

类似前述，以 9 为 源点的最短路径一共有 31 条。
所有路径如下示意：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
path-0 : [9, 6]
path-1 : [9, 7]
path-2 : [9, 8]
path-3 : [9, 10]
path-4 : [9, 6, 5]
path-5 : [9, 7, 5]
path-6 : [9, 8, 5]
path-7 : [9, 6, 5, 1]
path-8 : [9, 6, 5, 2]
path-9 : [9, 6, 5, 3]
path-10: [9, 6, 5, 4]
path-11: [9, 7, 5, 1]
path-12: [9, 7, 5, 2]
path-13: [9, 7, 5, 3]
path-14: [9, 7, 5, 4]
path-15: [9, 8, 5, 1]
path-16: [9, 8, 5, 2]
path-17: [9, 8, 5, 3]
path-18: [9, 8, 5, 4]
path-19: [9, 6, 5, 1, 0]
path-20: [9, 6, 5, 2, 0]
path-21: [9, 6, 5, 3, 0]
path-22: [9, 6, 5, 4, 0]
path-23: [9, 7, 5, 1, 0]
path-24: [9, 7, 5, 2, 0]
path-25: [9, 7, 5, 3, 0]
path-26: [9, 7, 5, 4, 0]
path-27: [9, 8, 5, 1, 0]
path-28: [9, 8, 5, 2, 0]
path-29: [9, 8, 5, 3, 0]
path-30: [9, 8, 5, 4, 0]

其他节点类似，此处不赘述。

要点

  • 此算法以 广度优先搜索 为指导基础，通过编号、构建 “最短路径树”、反转等算法过程，进而查找出图中的最短路径。
  • 构造树过程中，始终以图 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.

Shin一品老百姓

西北飘来一片云，忽而落在凤凰城。天黑幸有清风伴，明月照空作行灯。