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

路径查找算法和图搜索算法

｜

51

•

在这一步中，节点

A

到

B

再到

A

的距离，即

d(A,A)=6

，大于已经计算出的最短距

离（

0

），因此不更新其值。

•

到节点

D

（

6

）和

E

（

4

）的距离小于之前计算的距离，因此更新其值。

4.

接下来选择

E

。现在只有达到

D

（

5

）的累计总代价较小，因此仅更新该项。

5.

在最终计算

D

时，没有新的最小路径权重，故不更新，且算法终止。

尽管所有点对最短路径算法相对于并行计算每个节点而言更优，但对于大规

模的图来说，代价仍然高昂。如果只需要计算子类别节点之间的路径，则请

考虑使用子图。

4.5.2

　何时使用所有点对最短路径算法

当最短路径被阻塞或不够理想时，通常采用所有点对最短路径遴选替代路线，例如使用该

算法规划逻辑路线，可确保在各种路线选择情况下都有多条最佳路径。当需要考虑所有或

大部分节点之间的全部可能路径时，请使用所有点对最短路径算法。

示范用例如下。

•

优化城市设施配备和商品配送，例如确定交通网格不同区段的预期交通负载。更多内容

请参阅

R. C. Larson

和

A. R. Odoni

的著作“

Urban Operations Research

”。

•

可作为数据中心设计算法的一部分，用于查找带宽最大、延迟最低的网络。对于该方法

的详细介绍，参见

A. R. Curtis

等人的论文“

REWIRE: An Optimization-Based Framework

for Data Center Network Design

”。

4.5.3

　使用

Spark

实现所有点对最短路径算法

Spark ...