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

Question

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

我正在查看GraphX文档,但我无法找到方法来执行此操作.如果图形具有树结构,则还需要这样来计算图形的深度.他们是一个简单的方法吗？

Answer 1

要使用Spark GraphX查找顶点之间的最短路径,可以使用ShortestPaths对象,该对象是org.apache.spark.graphx.lib的成员.

假设你有一个GraphX图形g,你想找到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算法返回一个图形,其中顶点RDD包含格式的元组(vertexId, Map(target -> shortestPath).此图将包含原始图的所有顶点,以及它们Seq在算法参数中传递的所有目标顶点的最短路径.

在你的情况下,你想要两个特定顶点之间的最短路径,所以在上面的代码中我展示了如何只用一个target(v2)调用算法,然后我过滤结果只得到从所需顶点开始的最短路径(v1).