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

54

｜

第

4

章

或

或

或

或

图 4-9：单源最短路径算法的步骤

算法流程如下。

1.

算法从根节点开始，且所有路径都将从根节点开始度量。在图

4-9

中，我们选择节点

A

作为根节点。

2.

选择到根节点权重最小的关系，将该关系和与其关联的节点一起添加到树中，在本例中

就是

d(A,D)=1

。

3.

选择从根节点到各未访问节点中累计权重最小的下一个关系，以相同方式将该关系和关

联节点添加到树中。图

4-9

中的选项有

d(A,B)=8

、直接路线

d(A,C)=5

（按照

A-D-C

路

线，则权重为

4

）和

d(A,E)=5

。因此，选择

A-D-C

路线，并将

C

添加到树中。

4.

持续执行该过程，直到没有更多节点要添加为止，从而得到单源最短路径。

4.6.1

　何时使用单源最短路径算法

当需要求解从固定起始节点到其他各节点的最优路径时，可以采用单源最短路径算法。由

于该算法基于从根节点出发的路径总权重来选择路线，因此对查找根节点到各节点的最优

路径很有用，但是如果要在一次行程中访问所有节点，就不必采用该算法。

举例来说，单源最短路径算法对于确定急救服务的主要路线很有帮助，这种场景并不要求