Spark Scala GraphX：两个顶点之间的最短路径

Question

我在 Spark GraphX (Scala) 中有一个有向图 G。我想找到从已知顶点 v1 开始到达另一个顶点 v2 应该穿过的边数。换句话说，我需要从顶点 v1 到顶点 v2 的最短路径，以边数计算（不使用边的权重）。

我正在查看 GraphX documentation，但我无法找到实现它的方法。如果图形具有树结构，这也是计算图形深度所必需的。他们是一种简单的方法吗？

Answer 1

要使用 Spark GraphX 找到顶点之间的最短路径，有 ShortestPaths object, which is member of the org.apache.spark.graphx.lib。

假设您在 g 中有一个 GraphX 图，并且您想要找到 ID 为 v1 和 v2 的顶点之间的最短路径，您可以执行以下操作：

import org.apache.spark.graphx._
import org.apache.spark.graphx.lib.ShortestPaths

val result = ShortestPaths.run(g, Seq(v2))

val shortestPath = result               // result is a graph
  .vertices                             // we get the vertices RDD
  .filter({case(vId, _) => vId == v1})  // we filter to get only the shortest path from v1
  .first                                // there's only one value
  ._2                                   // the result is a tuple (v1, Map)
  .get(v2)                              // we get its shortest path to v2 as an Option object

ShortestPaths GraphX 算法returns 顶点 RDD 包含格式为 (vertexId, Map(target -> shortestPath) 的元组的图。该图将包含原始图的所有顶点，以及它们到算法 Seq 参数中传递的所有目标顶点的最短路径。

在你的例子中，你想要两个特定顶点之间的最短路径，所以在上面的代码中我展示了如何调用只有一个目标（v2）的算法，然后我将结果过滤到仅获取从所需顶点 (v1) 开始的最短路径。

Spark Scala GraphX：两个顶点之间的最短路径

Spark Scala GraphX: Shortest path between two vertices

scala

apache-spark

spark-graphx