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

40

｜

第

4

章

如前所述，搜索算法为图的遍历奠定了基础，下面看看路径查找算法，它根据跳数或

权重来查找代价最小的路径。权重可以是任何可度量的东西，比如时间、距离、容量或

成本等。

两种特殊的路径

图分析中有两种特殊的路径值得注意。第

1

种是

欧拉路径

，即每个关系恰好只被访问

一次。第

2

种是

哈密顿路径

，即每个节点恰好只被访问一次。一条路径既可以是欧拉

路径，也可以是哈密顿路径，而且如果在同一节点开始和结束，则可以称其为

环

或

回

路

。图

4-5

做了直观的对比。

欧拉环

且非哈密顿环

哈密顿环

且非欧拉环

访问每个关系一次

（允许重复节点）

访问每个节点一次

（允许重复关系）

欧拉环且哈密顿环

图 4-5：欧拉环和哈密顿环具有特殊的历史意义

第

1

章中的“哥尼斯堡七桥”问题实际上就是搜索一个欧拉环。很容易理解如何将其

应用于引导扫雪车和邮件投递这样的线路搜索场景。然而，也有一些算法利用欧拉路

径处理树结构中的数据，而且从数学角度来看要比研究其他类型的环更容易。

哈密顿环最广为人知的就是它与

旅行商问题

（

traveling salesman problem

，

TSP

）的关

系，该问题是：“对于旅行商而言，访问每个指定城市并返回原城市的最短路径是什

么？”虽然这看起来和欧拉环类似，但是

TSP

对于近似替代方案的计算更精确。它广

泛应用于各种规划、物流和优化问题中。

4.4

　最短路径算法

最短路径算法用于计算一对节点之间的最短（加权）路径。由于可以实时运行，因此它对

用户交互和动态工作流非常有用。

路径查找的历史可以追溯到

19

世纪，它被视为经典的图论问题。在 ...