$29
实现 Dijkstra 最短路径算法
(1)输入可以是有向图,也可以是无向图,从文本文件中读取图数据,可根据图示输入(节点数目不固定)构造输入文件
(2)可输出图的邻接表和邻接矩阵表示
(3)输出从某个顶点(可运行时指定,如顶点 0)到其他某个顶点,或所有顶点的最短路径及路径长度
输入图的文本文件为(每个数据行为一条边-起点 终点 边的权值):
1
0 3 3
0 4 6
1 2 2
1 5 4
2 5 5
3 7 5
4 6 9
5 6 4
5 7 4
6 2 5
6 5 3
输入文件为:
0
0 1 6
0 3 7
0 4 1
2 4 9
2 6 4
3 5 7
3 7 9
4 6 3
5 6 6
5 7 5
6 7 5
注意:
(1)输入文本中顶点用 0 开始的整数编号,边的权值为正整数;
(2)输入可以是有向图或无向图,从文件数据中去判断,第一行为 0 则是无向图,1 为有向图,输入的边数根据读入的数据进行判断;
(3)输入文本形成的图中可能存在非连通的顶点,特定顶点之间可能不存在最短路径;(4)可以不用考虑输入文件中存在的其他格式或数据类型错误
(5)可以不用考虑两个顶点之间存在重复的有向边或者无向边,无权值为 0 的边;
(6)可输出某个顶点出发的到所有节点的最短路径和路径长度,若无路径,输出 null 和 0;(7)可输出指定顶点之间的最短路径和路径长度;(8)输出结果形式参考测试样例
关于作业提交的一些要求:
●不要 DDL 前几分钟才提交,提交前检查压缩包内文件是否正确,提交后把提交的文件下
载后再检查一遍
●没实现的方法也要写上方法名,并按要求的类型输出返回值,保证测试代码调用方法编译不
出错
●不要带 package
●类名和方法名要符合要求
●不要导入奇奇怪怪的包
●不要用中文写代码,注释也不要
●如果代码在你本地都有红色警告就不要提交了,不能编译的直接 0 分
●什么都没做的不要交空文件,更不要交什么 word 文档
●尽量不要使用 java8 以上的 java 新特性(能直接换过来环境就给分,换不过来就没了) ●直接把所有 java 文件打包[zip] 上传,不要放进文件夹里,也不要单独交 java 文件