上机实验（第一次实验 5.17）1
需积分: 0 79 浏览量
2022-08-03
11:35:34
上传
评论
收藏 98KB PDF 举报
上机实验说明
题目：
1. 编程实现 Bellman-Ford 算法；
2. 编程实现 Floyd-Warshall 算法。
要求：
1. 在书上基本算法的基础上，增加计算前驱结点（前驱矩阵）的代码；
2. 加入输出最短路径的代码。计算完成后，根据前驱结点（前驱矩阵），依次输出每条
最短路径上从起点到终点的结点序列及其路径长度。
输入：
使用数据文件作为输入。数据文件为文本文件。
Bellman-Ford 的输入文件： bf.in
格式如下：
文件包含 n+1 行数据：
⚫ 第一行：有一个整数和一个字符串，第一整数表示下面有 n 条边的数据，
字符串是待求单源点最短路径的源结点名；
⚫ 第二~n+1 行：每行三个数据，第一个和第二个数据都是字符串，分别是边
的起点和终点的结点名称；第三个数据是整数，是这条边的权重（可以为
负数）。数据之间用一个空格隔开（注：字符串仅由数字符'0'~'9'和英文
字母组成，中间不包含任何其他字符）。
Floyd-Warshall 的输入文件： fw.in
格式基本同上，只是第一行只包含一个整数，表示下面有 n 条边的数据。第二~n+1
行的数据格式相同。
数据文件在学习群里下载
输出：
程序的计算结果为求得的所有最短路径，在屏幕上直接输出，格式如下：
⚫ 先输出你的学号和名字，学号和名字之间用空格隔开。换行。
⚫ 然后以每条最短路径一行的方式输出结果，先输出结点序列，然后是路径的长度。
⚫ 结点用输入文件中给出的名字表示，结点之间用减号“-”连接，路径长度与结点
序列间用一个空格隔开。
如：学生学号为 U201702133，姓名为张三，结果是结点 s 经过结点 x、结点 t 到结点 z，
长度为 5 和结点 1 经过结点 5、结点 6 到结点 7 ，长度为 9 的两条路径，则输出样式是：
U201702133 张三
s-x-t-z 5
1-5-6-7 9
提交方式：
完成后，将源程序和运行结果的截屏做在一个 word 文件里，文件命名格式为：
实验 1-姓名-学号.doc
然后发送到 1097412466@qq.com。
评论0