GraphX内置图算法2：最短路径算法
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。Dijkstra算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。算法思想是，每次找到离源点最近的一个顶点，然后以该顶点为中心，然后得到源点到其他顶点的最短路径。
对于图中的每个顶点，最短路径算法会找到为了到达起始顶点所需的最小的边数。Spark使用ShortestPaths对象实现了最短路径算法。它只有一个名为run的方法，该方法接受一个图和一个具有里程碑意义的顶点ID的序列。返回的图的顶点包含一个带有到每个地标的最短路径映射，其中地标性顶点ID是key，最短路径长度是value。
例如，如果我们想要将Wikispeedia中的“14th_century”与“Rainbow”这两个页面连接起来，那么需要的最小点击数是多少次？下面我们使用Spark GraphX来进行计算。
// 找出将"14th_century"与"Rainbow"页面连接起来的最少点击数
// 首先，需要找到两个页面的顶点ID
// articles.filter(x => x._1 == "Rainbow" || x._1 == "14th_century").collect().foreach(println)
val id_Rainbow = articles.filter(x => x._1 == "Rainbow").take(1)(0)._2
println("Rainbow的顶点ID是：" + id_Rainbow)
val id_14th_century = articles.filter(x => x._1 == "14th_century").take(1)(0)._2
println("14th_century的顶点ID是：" + id_14th_century)
执行以上代码，输出内容如下：
Rainbow的顶点ID是：3425 14th_century的顶点ID是：10
这样就获得了两个页面顶点的ID。然后调用ShortestPaths的run方法，用wikigraph和Seq中的一个ID作为参数，计算到给定地标顶点集的最短路径。
// run方法计算到给定地标顶点集的最短路径 import org.apache.spark.graphx.lib._ val shortest = ShortestPaths.run(wikigraph, Seq(3425)) // 最短距离图，其中每个顶点属性是一个Map映射，包含到每个可到达的地标顶点的最短路径距离 shortest.vertices.filter(x => x._1 == 10).collect.foreach(println)
输出内容如下所示：
(10,Map(3425 -> 3))
可以看出，要将“14th_century”与“Rainbow”页面连接起来，最少需要三次点击。
但是，ShortestPaths不会给出从一个顶点到另一个顶点的路径，只给出了需要到达它的边的数量。要在最短路径上找到顶点，需要编写自己的最短路径算法的实现，这超出了本书的范围。
