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

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

｜

41

路径。

1956

年，

Edsger Dijkstra

提出了其中最著名的一种算法。

Edsger Dijkstra

的最短路径算法首先查找从起始节点到与其直接连接的节点的最小权重关

系。该算法追踪这些权重并移动到“最近”的节点，然后针对当前节点执行同一计算，但

是现在的权重是从起始节点起算的累计值。算法继续执行，计算一条累计权重“曲线”，

总是选择累计权重最小的路径前进，直至到达目标节点为止。

在图分析中描述关系和路径时使用了

权重

、

代价

、

距离

和

跳

等术语。“权重”

是关系的某一特定性质的数值型取值。“代价”的用法与之类似，但更常用

于考察路径的总权重。

“距离”在算法中通常用于表示节点对之间的遍历代价，而且并不要求是实

际的距离。“跳”通常用来表示两个节点之间的关系数量。有时会组合使用

这些词，比如“到达伦敦的距离为

5

跳”或“那是这段距离的最小代价”。

4.4.1

　何时使用最短路径算法

基于跳数或加权关系值，使用最短路径算法可以找到节点对之间的最优路线，例如它可以

实时求解分离度以及点与点之间的最短距离或最经济的路线，也可以使用该算法直接探察

特定节点之间的连通情况。

示范用例如下。

•

查找两地间的行进方向。像谷歌地图之类的互联网地图工具可以使用最短路径算法（或

类似变体）提供驾驶导航服务。

•

找出社交网络中人与人之间的分离度，比如当你在

LinkedIn

上查看某人的资料时，图

中会显示你们之间相隔多少人，并列出双方的共有联系人。

•

根据某个演员和

Kevin Bacon

共同出演的电影来查找他们之间的距离 ...