scala - 使用 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 值。