数据分析之图算法: 基于Spark和Neo4j

50

｜

第

4

章

4.5.1

　近观所有点对最短路径算法

按照运算步骤的顺序很容易理解所有点对最短路径算法的计算过程。图

4-8

演示了节点

A

的处理步骤。

所有节点的初始距离

设置为∞，之后起始

节点的距离设置为0

第1步

从A出发

第2步

从A到C再到

下一节点

第3步

从A到B再到

下一节点

第4步

从A到E再到

下一节点

第5步

从A到D再到

下一节点

每一步都保留或更新到目前为止计算出的最小值

仅给出从节点A到其他各节点的计算步骤

图 4-8：计算从节点 A 到其他各节点最短路径的步骤，更新步骤用阴影标出

该算法最初假定到所有节点的距离都为无穷大。选定起始节点后，将到该节点的距离设为

0

。计算过程如下。

1.

从起始节点

A

开始，计算移动到可达节点的代价并更新值。为了寻找最小值，可以选择

B

（代价为

3

）或

C

（代价为

1

）。选定

C

作为下一阶段遍历的起始节点。

2.

现在从节点

C

开始，算法更新从

A

到那些直接由

C

可达的节点的累计距离。只有当代

价更小时，才会更新值。

A=0, B=3, C=1, D=8, E=∞

3.

然后选择

B

作为未访问的下一最近节点。它与节点

A

、

D

和

E

都有关系。算法将

A

到

B

的距离与

B

到每个节点的距离相加，计算出

A

到这些节点的距离。注意，从起始节点

A

到当前节点的最小代价始终作为沉没成本保留。距离（

d

）计算结果如下：

d(A,A) = d(A,B) + d(B,A) = 3 + 3 = 6

d(A,D) = d(A,B) + d(B,D) = 3 + 3 = 6

d(A,E) = d(A,B) + d(B,E) = 3 + 1 ...