本人最近研究關于spark的圖模型，spark最近才接觸，scala語言也不是很熟，論壇里有沒有高手幫忙解答一下關于最短路徑的，官方檔案我也看了，但貌似沒有關于最短路徑的，那個shortestpaths原始碼，也沒怎么看明白，而且一下實作辦法也只是展示了源點到目標頂點的距離，我想用spark做出最短路徑的，最好是有代碼案例的，結果帶中間節點的，不知哪位大神做過這方面的研究，幫幫忙
uj5u.com熱心網友回復：
不知道樓主解決了么，我這給你個例子：import org.apache.spark.{SparkConf, SparkContext}
import org.apache.spark.graphx.{EdgeDirection, VertexId, Graph}
import org.apache.spark.graphx.util.GraphGenerators
object Pregel_SSSP {
def main(args: Array[String]) {
val conf = new SparkConf().setAppName("Pregel_SSSP")
val sc = new SparkContext(conf)
// A graph with edge attributes containing distances
val graph: Graph[Long, Double] =
GraphGenerators.logNormalGraph(sc, numVertices = 5).mapEdges(e => e.attr.toDouble)
graph.edges.foreach(println)
val sourceId: VertexId = 0 // The ultimate source
// Initialize the graph such that all vertices except the root have distance infinity.
val initialGraph : Graph[(Double, List[VertexId]), Double] = graph.mapVertices((id, _) => if (id == sourceId) (0.0, List[VertexId](sourceId)) else (Double.PositiveInfinity, List[VertexId]()))
val sssp = initialGraph.pregel((Double.PositiveInfinity, List[VertexId]()), Int.MaxValue, EdgeDirection.Out)(
// Vertex Program
(id, dist, newDist) => if (dist._1 < newDist._1) dist else newDist,
// Send Message
triplet => {
if (triplet.srcAttr._1 < triplet.dstAttr._1 - triplet.attr ) {
Iterator((triplet.dstId, (triplet.srcAttr._1 + triplet.attr , triplet.srcAttr._2 :+ triplet.dstId)))
} else {
Iterator.empty
}
},
//Merge Message
(a, b) => if (a._1 < b._1) a else b)
println(sssp.vertices.collect.mkString("\n"))
}
}
uj5u.com熱心網友回復：
基于spark 1.3的uj5u.com熱心網友回復：
你好，這是求單源最短路徑，怎么才能并行求多源路徑。我嘗試把他寫成方法呼叫，然后把需要求得點對生產rdd,再map呼叫單源方法，但rdd不能嵌套rdd。另一方面，我感覺他肯定是可以并行的，因為求每一個結點單源路徑和其他結點不相關，只是不知道怎么并行。急求！！！uj5u.com熱心網友回復：
注意下單源的實作思路，就是迭代程序中記錄下當前的最短距離，現在變成了多源，就需要分別記錄多個路徑的相對最短距離，attr里就需要一個映射關系。并不是簡單的并行對每一個點對執行單源的演算法和資料結構就可以的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/77286.html
標籤：Spark