MATLAB实验报告

《MATLAB及应用》

实验报告

实践选题： MATLAB下Dijstra算法的实现专业班级：2010级信管1班

指导教师：周宏宇

姓名及学号：吴亮

学号（100903012）

成绩评定：

安阳师范学院《MATLAB及应用》课外实践报告

成绩评定：

学号100903012 学生姓名吴亮专业班级10级信管1班课程设计

（论文）

题目

MATLAB下Dijkstra算法的实现

课

程

设计

（论文）任务

在掌握Dijkstra算法的基础上，综合运用《物流运输与配送》、《运筹学》、《物流学》等课程理论知识，学会利用MATLAB软件编制设计程序，提高理论与实际相结合的应用能力。

要求运用节约法进行配送线路设计，解决课程设计指导书上案例3，计算应用MA TLAB 软件。编写设计程序，并调试运行，完成以下任务：

（1）同组同学每人以一个不同的节点作为出发点手动进行最短路的计算；

（2）利用MA TLAB软件编写程序，以案例3的数据作为默认数据对Dijkstra算法程序进行测试；

（3）实现输入数据的界面操作；

（4）输入起始点和终点能够自动计算最短路径里程及最短路径。

完成课程设计说明书。主要内容包括：Dijkstra算法的原理、程序框图、部分主要程序及说明、最终结果、结果分析及任务书上要求完成的内容等。

指

导

教

师

评

语

及

成

绩成绩：指导教师签字：

年月日

目录

一．设计目的 (3)

二．Dijkstra算法的原理 (3)

2.1 两个指定顶点之间的最短路径 (3)

2.2 Dijkstra算法原理 (3)

三．Dijkstra算法的操作步骤 (4)

四．Dijkstra算法的程序框图 (4)

4.1菜单程序框图 (4)

4.2输入程序框图 (5)

4.3 main框图 (6)

五．部分主要程序及其说明 (8)

5.1菜单menu程序 (8)

5.2原始数据default_dat程序 (8)

5.3输入数据input_dat程序 (9)

5.4迪杰斯特拉算法main程序 (9)

六．主要任务 (11)

6.1最短路的计算 (11)

6.2测试 (12)

6.2.1测试1 (12)

6.2.2测试2 (13)

6.3实现输入数据界面 (14)

6.4最短路径求取 (14)

参考文献 (15)

MATLAB 下Dijkstra 算法的实现

一．设计目的

物流运输与配送课程设计是在学生必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识.

1.培养学生综合运用《物流学》、《物流运输与配送》、《运筹学》等课程理论知识的能力。

2.培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利用MATLAB 软件进行程序设计，提高理论与实际相结合的应用能力。

3.能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合运用能力。

二．Dijkstra 算法的原理

2.1 两个指定顶点之间的最短路径

问题如下：给出了一个连接若干个客户的道路网络，在这个网络的两个指定客户间，找一条最短的路线。

以各客户为图G 的顶点，两客户间的直通路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数w(e)—直通路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点0u ，0v 间的具最小权的轨。这条轨叫做0u ，0v 间的最短路，它的权叫做0u ，0v 间的距离，亦记作()00,d u v 。求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。

2.2 Dijkstra 算法原理

Dijkstra 算法原理

[1]

：首先，引进一个辅助向量D ，它的每个分量D 表示当前所找到的

从始点v 到每个终点i v 的最短路径的长度。如D[3]=2表示从始径相对最小长度为2。这里

强调相对就是说在算法过程中D 的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v 到i v 有弧，则D 为弧上的权值；否则置D 为∞。显然，长度为 []D j Min = {|i D v ∈V} 的路径就是从v 出发的长度最短的一条最短路径。此路径为(,)j v v 。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是k v ，则可想而知，这条路径或者是(v, k v )，或者是(v, j v , k v )。它的长度或者是从v 到k v 的弧上的权值，或者是[]D j 和从j v 到k v 的弧上的权值之和。 一般情况下，假设S 为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X ）或者是弧(v,x)，或者是中间只经过S 中的顶点而最后到达顶点X 的路径。因此，下一条长度次短的最短路径的长度必是[]D j Min ={|i D v ∈V-S}其中，D 或者是弧(v, i

v )上的权值，或者是[]D k

(

k v ∈S)和弧(k

v ,i

v )上的权值之和。

（1）arcs 表示弧上的权值。若不存在，则置arcs 为∞。S 为已找到从v 出发的最短路径的终点的集合，初始状态为空集。那么，从v 出发到图上其余各顶点i v 可能达到的最短路径长度的初值为D arcs = [Locate Vex(G ,v),i] i v ∈V ；

（2）选择vj ，使得[]D j Min ={|i D v ∈V-S}；

（3）修改从v 出发到集合V-S 上任一顶点k v 可达的最短路径长度。

三．Dijkstra 算法的操作步骤

Dijkstra 算法的操作步骤

[1]

：

1．初始时令回路0{}S V =，T={其余顶点}，T 中顶点对应的距离值若存在0,i V V ，

0(,)i d V V 为0,i V V 弧上的权值，若不存在0,i V V ，0(,)i d V V 为 ∞；

2．从T 中选取一个其距离值为最小的顶点W 且不在S 中，加入到S 中；

3. 对T 中顶点的距离值进行修改：若加进W 作中间顶点，从0V 到i V 的距离值比不加W 的路径要短，则修改此距离值；

4. 重复上述步骤2、3直到S 中包含所有顶点，即S=T 为止。

四．Dijkstra 算法的程序框图

4.1菜单程序框图

主菜单的程序是使界面上直接显示所需完成的内容，主要完成默认数据导入，输入数据，查看数据，求取路径，退出程序的任务，其具体程序的框图如下图 图1 菜单程序menu 框图 所示。

输入全局变量 length,i,j

adj_mat=zeros(length);

i=1

i

i=i+1;j=i

Y

skip

N

j

Y

skip

N

j=j+1

i=j

adj_mat(i,j)=input(‘:’);adj_mat(j,i)=adj_mat(i,j)

Y

结束

skip

N

图1 菜单menu 程序框图

4.2输入程序框图

输入程序是为了完成从外界输入数据形成一个新的邻接矩阵，产生一组新的数据进行最短路的求解。输入程序框图如下图 图2 输入input_dat 程序框图 所示。

输入全局变量 length,i,j

adj_mat=zeros(length);

i=1

i

i=i+1;j=i

Y skip

N

j

Y skip

N

j=j+1

i=j

adj_mat(i,j)=input(‘:’);adj_mat(j,i)=adj_mat(i,j)

Y

结束

skip

N

图2 输入input_dat 程序框图

4.3 main 框图

main 程序是这个系统的主程序，它完成的从任一结点开始到指定的结点为止的最短路程。main 框图如下图 图3 main 框图 所示。

开始

定义变量m ，adj_mat(),i j,lengs ，paths ，know ，sta ，dst,k 初始化 变量know （1）=sta ，

index=1

输入k=1i<=m

Y i=sta N

Lengs(i)=adj_mat(sta,i)

lengs(i)=inf

N

Paths(i)=sta

i=i+1

skip

N

skip

Y

skip

Y

i<=m

Y i=i+1

i=sta

skip

Y

min=inf

N

j<=m

skip

N

skip

N

j=j+1

Y lengs(j)<=min

k=j;min=lengs(j)

Y

skip N

j<=m

skip

N

j=j+1

Y lengs(i)+adj_mat(I,j)

skip

N

lengs(j)=lengs(i)+adj_mat(i,j);

Paths(j)=i

Y

leng=lengs(dst);

k=dst

输出leng

j=1；path=dst

k=paths(k);path=[k path]

paths(k)=sta

N

path=[sta path]

输出path(k)

结束

Y

图3 main 框图

五．部分主要程序及其说明

5.1菜单menu程序

choice = input('欢迎来到dijkstra算法求取最短路径系统\n请选择:\n1.使用默认数据 2.输入数据\n3.查看数据 4.求取路径\5.退出程序\n' ); elseif choice == 3

disp(adj_mat);

elseif choice == 4

sta = input('请输入起始结点:');

dst = input('请输入目的地:');

if sta == dst

fprintf('\r\n');

else

[leng,path] = main program(adj_mat , sta , dst);

fprintf('%d\n',leng);

k = length(path);

fprintf('经过路径为:');

for i = 1:1:k-1

fprintf('%d ---->',path(i));

end

fprintf('%d\n',path(k));

end

end

该段程序完成的是从菜单界面进入程序并选择完成的任务。

当输入值为1时，程序默认使用原始数据程序即default_dat，并在界面上输出默认数据已被启用。

当输入值为2时，程序调用输入程序即input_dat。

当输入值为3时，程序输出数据，并在界面上显示。

当输入值为4时，程序调用迪杰斯特拉算法程序即main，并在界面上输入起始点和目的点，通过main的计算，能输出最短路径和经过的路径。

当输入值为5时，退出程序。

5.2原始数据default_dat程序

function adj_mat=default_dat() %定义原始数据函数

length=10; %定义结点个数

adj_mat=zeros(length); %邻接矩阵

adj_mat(1,1)=0;adj_mat(1,2)=8;adj_mat(1,3)=5;adj_mat(1,4)=9;adj_mat(1,5)=12;adj_ mat(1,6)=14;adj_mat(1,7)=12;adj_mat(1,8)=16;adj_mat(1,9)=17;adj_mat(1,10)=22; %原始数据

该段程序通过定义结点个数来确定邻接矩阵的宽度，并能输入案例上的的数据，用其来进行测试。

5.3输入数据input_dat程序

function adj_mat =input_dat() %定义输入数据函数length = input('请输入节点的数量'); %定义结点个数

adj_mat=zeros(length); %定义一个邻接矩阵

for i =1:1:length

for j =i:1:length

if i ~= j

fprintf('请输入结点%d到结点%d的长度(没有则输入0)',i,j)

adj_mat(i,j) = input(':'); %输入结点间的距离

if adj_mat(i,j) == 0

adj_mat(i,j) = inf;

end

adj_mat(j,i) = adj_mat(i,j); %对称成为一个完整的对称矩阵

end

end

end

该段程序完成的是输入数据的过程，通过在界面上输入的结点数，以及从各结点到其后面的结点之间的距离，在对输入的数据进行对称，使其成为一个完整的矩阵，为以后的计算做铺垫。

5.4迪杰斯特拉算法main程序[3]

m=length(adj_mat); %定义m的长度

lengs =linspace(0,0,m); %产生行矢量

for i = 1:1:m

if i ~= sta

lengs(i) = adj_mat(sta,i);

if lengs(i) ~= inf

paths(i) = sta;

end

end

end

%for循环求起始点到各邻点的距离

index = 1; %标号

for i = 1:1:m

if i ~= sta

min = inf; %让最小值min为∞

for j = 1:1:m

if lengs(j) <= min

k = j;

min = lengs(j);

end

end

%for循环求最小值，并将lengs(j)的值赋给min，最后确定距起始点最近的点know(index) = k;

index=index+1;

for j = 1:1:m

if (lengs(i) + adj_mat(i,j)) < lengs(j)

lengs(j) = lengs(i) + adj_mat(i,j);

paths(j) = i;

end

end

%for循环球最短路并确定结点

end

end

%循环计算，求取最短路的距离

该段程序是完成dijkstra算法的主要程序。在该段程序中先定义一个起点，再从起点出发将起点的邻接矩阵求出，并从中找出距离起点最近的点作为下一个起点，再从该起点出发求其邻接矩阵，找出该邻接矩阵以及上一个邻接矩阵中除

该点外的其他距离中最小的值所表示的结点作为新的起点，以此类推，直到求到目的结点为止。如此即可完成dijkstra 算法，求出从已知起点到目的点的最短距离及其具体的路径。

六．主要任务

6.1最短路的计算

选择节点10为基点可得：

0i =，0i V =，j V =∞，M={1,2,3,4,5,6,7,8,9}

11010122V V D =+=；21010222V V D =+=；31010317V V D =+=；41010418V V D =+=；51010515V V D =+=；61010616V V D =+=；71010711V V D =+=；81010811V V D =+=；91010910V V D =+=

min 910V V ==，9j =，即10 -->9

9i =，10i V =，j V =∞，M={1,2,3,4,5,6,7,8,}

1191101727V V D =+=+=；

2192101424V V D =+=+=；

3193101222V V D =+=+=；

4194101525V V D =+=+=；5195101525

V V D =+=+=；

619610818V V D =+=+=；

719710616V V D =+=+=；8198101121V V D =+=+= min 711V V ==，7j =，即10 -->7

7i =，11i V =，j V =∞，M={1,2,3,4,5,6,8}

1771111223V V D =+=+=；

2772111122V V D =+=+=；

377311718V V D =+=+=；

4774111021V V D =+=+=；5775111021

V V D =+=+=；

677611920V V D =+=+=；

877811819V V D =+=+= min 811V V ==，8j =，即10 -->8

8i =，11i V =，j V =∞，M={1,2,3,4,5,6}

1881111627V V D =+=+=；

2882111829

V V D =+=+=；

3883111223V V D =+=+=；

488411718V V D =+=+=；588511617V V D =+=+=；6886111425V V D =+=+= min 515V V ==，5j =，即10 -->5

5i =，15i V =，j V =∞，M={1,2,3,4,6}

1551151227

V V D =+=+=；

2552151732

V V D =+=+=；

355315924V V D =+=+=；

455415318V V D =+=+=；655615823V V D =+=+= min 616V V ==，6j =，即10 -->6

6i =，16i V =，j V =∞，M={1,2,3,4}

1661161430V V d =+=+=；

266216824

V V d =+=+=；

3663161127V V d =+=+=；

4664161733V V d =+=+= min 317V V ==，3j =，即10 -->3

3i =，17i V =，j V =∞，M={1,2,4}

133117522V V d =+=+=；233217926V V d =+=+=；433417724V V d =+=+= min 418V V ==，4j =，即10 -->4或10 -->8-->4或10 -->5-->4

4i =，18i V =，j V =∞，M={1,2}

144118927V V d =+=+=；2442181533V V d =+=+= min 122V V ==，1j =，即10 -->1或10 -->3-->1

1i =，22i V =，j V =∞，M={2}

211222830V V d =+=+=

min 222V V ==，2j =，即10 -->2或10 -->7-->2

最后得到的具体结果如下所示：

起点为10点，终点为1点的最短距离为22，其路径为10 -->1或10 -->3-->1。 起点为10点，终点为2点的最短距离为22，其路径为10 -->2或10 -->7-->2。 起点为10点，终点为3点的最短距离为17，其路径为10 -->3。

起点为10点，终点为4点的最短距离为18，其路径为10 -->4或10 -->8-->4或10 -->5-->4。

起点为10点，终点为5点的最短距离为15，其路径为10 -->5。 起点为10点，终点为6点的最短距离为16，其路径为10 -->6。 起点为10点，终点为7点的最短距离为11，其路径为10 -->7。 起点为10点，终点为8点的最短距离为11，其路径为10 -->8。 起点为10点，终点为9点的最短距离为10，其路径为10 -->9。

6.2测试 6.2.1测试1

以案例3的数据作为默认数据对Dijkstra 算法程序进行测试。现取10点为起始点，以2点为终点。其手动计算结果为最短路径长度为22，其路径是10 -->2。通过MATLAB 计算

得到结果如下图4 测试结果1 所示。

图4 测试结果1

6.2.2测试2

现取10点为起始点，以8点为终点。其手动计算结果为最短路径长度为11，其路径是10 -->8。通过MATLAB计算得到结果如下图5 测试结果2 所示。

图5 测试结果2

通过以上随机取的两组数据，经过MATLAB的计算与手动的计算，可以看出其结果是完全相同的，能够判断出Dijkstra程序的准确性。

6.3实现输入数据界面

进行菜单选择的界面操作如图6 菜单选择界面所示。在该界面可以完成使用默认数据，输入数据，查看数据，求取路径和退出程序等功能。而且使用该界面能更直观的让使用者使用。

图6 菜单选择界面

以下是实现输入数据与查看数据的任务，在该过程中，可以输入结点的数量，并能输入各结点之间的距离，显示一个对称的矩阵，为以后的求解做准备。其具体的操作步骤如图7 输入数据所示。

图7 输入数据

6.4最短路径求取

该程序可以完成输入起始点和终点能够自动计算最短路径里程及最短路径。

现输入4个结点，且结点1到结点2的距离为2，结点1到结点3的距离为4，结点1到结点4的距离为5，结点2到结点3的距离为6，结点2到结点4的距离为2，结点3到结点4的距离为3。现计算结点1到结点4的距离，其最短路径为4，路径是1 -->2-->4。使

用MA TLAB程序计算其结果如图8 求取结果所示。

如图8 求取结果参考文献

参考文献

[1] 赵晓川.物流配送系统规划[M].北京：中国水利水电出版社，2007.

[2] 林雪松，周婧，林德新. MATLAB7.0应用集锦. 北京：机械工业出版社，2005.

[3] 代西武.Dijkstra 矩阵算法[D].北京：北京建筑工程学院基础科学部，2007

[4] 张志涌，杨祖樱等.MATLAB教程7.0[M].北京：北京航空航天出版社，2005.