2实验5 最短路求解的编程实现.docx

1、2实验5 最短路求解 的编程实现实验5 最短路问题的编程实现成绩专业班级 数学111班 学号 201112010129姓名 张诚 报告日6.16 .实验类型：验证性实验 综合性实验 设计性实验实验目的：熟练最短路问题的floyd算法。实验内容：最短路问题的floyd算法。实验原理 最短路问题的floyd算法：从邻接矩阵出发，利用三角和算法不断加入点，对距离矩阵进行修正，直到所有的点都加完，即求出了任意两点间的最短距离矩阵。实验步骤1 要求上机实验前先编写出程序代码 2 编辑录入程序3 调试程序并记录调试过程中出现的问题及修改程序的过程4 经反复调试后，运行程序并验证程序运行是否正确。5 记录运

2、行时的输入和输出。 预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：D为任意两点的最短路。参考程序functionD,S=floyd(d)ss=size(d)s=ones(ss)n=ss(1)for i=1:n for j=1:n s(i,j)=j endendfor k=1:n for i=1:n for j=1:n if d(i,j)d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j) s(i,j)=s(i,k) end end endendD=dS=s d=0 1 2 4 4 7;inf 0 3 3 5 6;inf inf 0 2 2 5;in

3、f inf inf 0 inf 3;inf inf inf inf 0 6;inf inf inf inf inf 0d = 0 1 2 4 4 7 Inf 0 3 3 5 6 Inf Inf 0 2 2 5 Inf Inf Inf 0 Inf 3 Inf Inf Inf Inf 0 6 Inf Inf Inf Inf Inf 0 D,S=floyd(d)ss = 6 6s = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1n = 6s = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

4、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1

5、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 1 1 1 1 1 1

6、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1

7、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3

8、 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3

9、 4 5 6 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3

10、 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 1 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 1 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 1 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3

11、 4 5 6 1 2 3 4 5 6 1 2 3 4 5 1 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 1 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3

12、 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 1 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 1 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 1s = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6D = 0 1 2 4 4 7 Inf 0 3 3 5 6 Inf

13、 Inf 0 2 2 5 Inf Inf Inf 0 Inf 3 Inf Inf Inf Inf 0 6 Inf Inf Inf Inf Inf 0S = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6D = 0 1 2 4 4 7 Inf 0 3 3 5 6 Inf Inf 0 2 2 5 Inf Inf Inf 0 Inf 3 Inf Inf Inf Inf 0 6 Inf Inf Inf Inf Inf 0S = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6