使用pregel graphx实现一对一最短路径

Question

我尝试使用link中的代码找到从单个源到n个顶点的最短路径

val graph: Graph[Long, Double] =
  GraphGenerators.logNormalGraph(sc, numVertices = 100).mapEdges(e => e.attr.toDouble)
val sourceId: VertexId = 42

val initialGraph = graph.mapVertices((id, _) =>
    if (id == sourceId) 0.0 else Double.PositiveInfinity)
val sssp = initialGraph.pregel(Double.PositiveInfinity)(
  (id, dist, newDist) => math.min(dist, newDist),
  triplet => {
    if (triplet.srcAttr + triplet.attr < triplet.dstAttr) {
      Iterator((triplet.dstId, triplet.srcAttr + triplet.attr))
    } else {
      Iterator.empty
    }
  },
  (a, b) => math.min(a, b)
)
println(sssp.vertices.collect.mkString("\n"))

它给我提供了从42到N个顶点的最短路径。然而，如何找到从单一来源到单一目的地的最短路径？例如，source=42，dest = 135，那么我想找出它们之间的最短路径。

谢谢

Answer 1

你不能找到两个顶点之间的最短距离，也就是说，如果不探索整个图。因为，即使您在目的地收到消息后停止探索，也无法保证这是最短的距离。因此，这个算法在复杂度方面是很好的。您应该只从获得的不同目标中选择sssp值。