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

48

｜

第

4

章

运行该程序，结果如下所示：

place cost

Den Haag 0.0

Hoek van Holland 27.0

Felixstowe 234.0

Ipswich 256.0

Colchester 288.0

London 394.0

结果与使用最短路径算法的相同，但对于更复杂的数据集而言，由于需要计算的路径更

少，因此

A*

算法速度更快。

4.4.6

　最短路径算法的变体

：

Yen

的

k

最短路径算法

Yen

的

k

最短路径算法（简称

Yen

算法）与最短路径算法类似，但是它并不仅仅查找两对

节点之间的最短路径，它还计算了第二最短路径、第三最短路径等，直到最短路径的第

k

–1

个偏差值。

Jin Y. Yen

于

1971

年提出该算法，并在论文“

Finding the K Shortest Loopless Paths in a Network

”

中做了系统阐述。当查找绝对最短路径并非唯一目标时，用该算法可获取替代路径。当需

要一个以上的备选计划时，该算法非常有用。

使用

Neo4j

实现

Yen

算法

下面的查询执行

Yen

算法来查找

Gouda

（高达）和

Felixstowe

之间的最短路径。

MATCH

(

start

:Place {id:"Gouda"}),

(end:Place {id:"Felixstowe"})

CALL algo.kShortestPaths.stream(

start

, end, 5, "distance")

YIELD index, nodeIds, path, costs

RETURN

index, ...