Spark: Single-Source Shortest Path 问题: 想象一个图包含 点,边和每条边的权重。 (https://i1.wp.com/algorithms.tutorialhorizon.com/files/2018/03/Weighted-Graph.png?ssl=1) 图中的路径可以定义为连续节点的集合,比如在顺序中从一个节点到下一个节点有一条边。两个节点之间的最短路径可以定义为路径上所有边的总权重最小的路径。例如,节点1到节点4的最短路径是距离为4的Node1-> Node3 -> Node4。 在这次作业中,需要计算从开始节点(STARTING_NODE = N1)到所有其他节点的距离。 请考虑以下tips当你实现方法时: • 在作业中假设没有其他多余的节点,这意味着每个节点至少有一条边到其他点。 • 两个独立节点之间的边的最小权重值为1。 • 你需要使用 Spark Core(不是GraphX或相似的方法)去解决这个问题。 • 输出必须按最短路径长度排序(升序)。 • 输出应该写入一个txt文件({zid}_output.txt)。 • 输出应符合以下格式(如下例子中所示),包含3列,逗号分隔:第一列包含目标节点,接下来是第二列最短路径的长度,以及从起始节点到目标节点的实际最短路径。 • 不能假设开始节点总是N0(可以是任意给出的点)。 • 可以下载示例输入 (https://github.com/mysilver/COMP9313/blob/master/graph.txt) , 和预期输出(https://github.com/mysilver/COMP9313/blob/master/shortest-pathes) . 输入格式: 可以假设输入表示一个连通有向图。 输入如下所示(和上面的图一样的graph)。输入文件的每一行表示图形的一个点,其格式类似于:起始节点、结束节点和距离。 N0,N1,4 N0,N2,3 N1,N2,2 N1,N3,2 N2,N3,7 N3,N4,2 N4,N0,4 N4,N1,4 N4,N5,6 输出格式 输出的格式应该如下所示。输出的每一行表示从起始节点到另一个节点的距离,其格式为:目标节点、最短距离和从起始节点到目标节点的路径。文件按最短路径排序: N2,3,N0-N2 N1,4,N0-N1 N3,6,N0-N1-N3