实验6最短路求解 的编程实现

实验6 最短路问题的编程实现

成绩

专业班级 信息123 学号 201212030317 姓名 李帅 报告日期

实验类型：●验证性实验 ○综合性实验 ○设计性实验 实验目的：熟练最短路问题的Dijkstra算法。 实验内容：最短路问题的Dijkstra算法。 实验原理 最短路问题的Dijkstra算法：首先对图中的所有节点赋予双标号,即临时

标号和永久标号,然后按一定的策略,依次判断并修改节点的临时标号,知道最后将终点改为永久标号求出最短路径。

实验步骤

1 要求上机实验前先编写出程序代码 2 编辑录入程序

3 调试程序并记录调试过程中出现的问题及修改程序的过程 4 经反复调试后，运行程序并验证程序运行是否正确。 5 记录运行时的输入和输出。

实验报告：根据实验情况和结果撰写并递交实验报告。

问题：求解下图中的v(1)到v(3)的最短路径：

v1 4 5 4 -2 -3 v2 v5 2 6 v4 8 v3

参考程序：function [d,r]=floyd(a) n=size(a,1); d=a; for i=1:n

for j=1:n r(i,j)=j; end end r

for k=1:n for i=1:n

for j=1:n

if d(i,k)+d(k,j)

运行结果：

>> a=[0 5 1000 1000 1000;1000 0 6 1000 -3;1000 1000 0 1000 2;4 1000 8 0 1000;4 1000 1000 -2 0] a =

0 5 1000 1000 1000 1000 0 6 1000 -3 1000 1000 0 1000 2 4 1000 8 0 1000 4 1000 1000 -2 0 >> [d,r]=floyd(a) d =

0 5 8 0 2 -1 0 3 -5 -3 4 9 0 0 2 4 9 8 0 6 2 7 6 -2 0 r =

1 2 2 2 2 5 2 5 5 5 5 5 3 5 5 1 1 3 4 1 4 4 4 4 5

d（i，j）表示从v（i）到v（j）的最短路程，例如v(1)到v(3)的最短路程为d（1,3）=8； 此时路径为r（1，3）=2到r（2，3）=5,到r（5,3）=4到r（4,3）=3结束，及最短路径

为v（1）->v(2)->v(5)->v(4)->v(3)。

实验总结：此程序横好的解决了最短路的求解问题，在此前首先要将图中各点的距离转化为矩阵在进行求解。