Starting from:
$35

$29

Homework 4 Solution

实现 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 文件

More products