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
…
提交截止日期：
2019/11/18 17:59 星期一
建立Project：
获取添加独立的Spark到project中：
•在eclipse中创建一个新的Java Project。
•下载Spark-Core.jar https://www.dropbox.com/s/xragkjaio6n9onp/Spark-Core.jar?dl=0
(https://www.dropbox.com/s/xragkjaio6n9onp/Spark-Core.jar?dl=0)
•添加到project中：右键点击project；next: Build Path > Add External archives。
提交project
您的代码必须(全部)包含在文件AssigTwo{zid}.java中。任何有编译错误的解决方案在整个作业中得到的分数都不会超过5分。
需要在提交文件之前进行测试，以确保可以在CSE的终端上编译/运行：
$ javac -cp “.:Spark-Core.jar” AssigTwo{zid}.java
$ java -cp “.:Spark-Core.jar” AssigTwo{zid} STARTING_NODE INPUT_PATH OUTPUT_PATH
登陆到任意CSE服务器上并使用give命令提交：
$ give cs9313 assig2 AssigTwo{zid}.java
你需要使用自己的zid代替{zid}。
也可以使用WebCMS或Give提交：
https://cgi.cse.unsw.edu.au/~give/Student/give.php (https://cgi.cse.unsw.edu.au/~give/Student/give.php)
如果你的作业提交超过一次，我们将只考虑最后一次提交。如果您在提交代码时遇到任何问题，请发送电子邮件给课程管理员(Maisie Badami, [email protected] (mailto:[email protected]))。
评估
您的源代码将根据可读性和易于理解的程度被手动检查和标记。我们将运行您的代码来验证它是否产生正确的结果。代码文档(即源代码中的注释)也很重要。以下是一项指示性评核计划(最高25分):
1. 输出由Apache Spark Core正确生成(12分)
2。输出格式正确，如规范中所述(3分)
格式应为
N2,3,N0-N2
N1,4,N0-N1
3.输出必须按照最短路径长度排序(升序) (4分)
4. 代码可以在CSE机器上执行，如作业规范所述(2分)
5. 文档和代码结构。在这里，您可以在程序开始时用一小段话(不超过300个单词)清楚地解释您的解决方案，并提供描述每个类正在做什么的注释。(4分)
迟交惩罚：第一天扣分10%，以后每天扣分30%。
Reviews
There are no reviews yet.