最新精品实验7 最小树与最短路问题实验.doc

实验7 最小树与最短路问题实验
1. 背景知识
Matlab是一个基于矩阵的工程计算软件,我们可以用Matlab来求解最短路问题。
WinQSB是Quantitative Systems for Business的缩写,WinQSB是一种教学软件,里面有大量的模型,对于非大型的问题一般都能计算,较小的问题还能演示中间的计算过程。我们用WinQSB来求解最小树和最短路问题。
2. 实验目的
(1)熟悉最小树与最短路问题的Matlab/WinQSB求解。
(2)通过求解一个最小树与最短路问题的建模和求解。
3. 工具及准备工作
(1)在开始实验前,需要回顾理论教材中有关最小树与最短路问题的内容。
(2)准备一台安装了Matlab和WinQSB软件的电脑。
4. 实验内容与步骤
例题1
(1)模型1(教材第308页例11)如下:
(2)求解思想:根据dijkstra算法计算。
(3)Matlab求解
()在Matlab的编辑窗口中输入以下内容:
% a=[0 6 3 1 inf inf inf inf inf;inf 0 inf inf 1 inf inf inf inf;
% inf 2 0 2 inf inf inf inf inf;inf inf inf 0 inf 10 inf inf inf;
% inf inf inf 6 0 4 3 6 inf;inf inf inf inf 10 0 2 inf inf;
% inf inf inf inf inf inf 0 4 inf;
% inf inf inf inf inf inf inf 0 inf;
% inf inf inf inf 2 inf inf 3 0]
function [mindistance,prepoint,endpointdistance,endpointpath]=dijkstra(a,endpoint)
n=size(a,1);
checkedpoints=zeros(1,n);
checkedpoints(1)=1;
mindistance=inf(1,n);
mindistance(1)=0;
prepoint=zeros(1,n);

while sum(checkedpoints)<n
findminpoint=0;
findminpointmindistance=inf;
for i=1:n
if checkedpoints(i)==1
for j=1:n
if ((checkedpoints(j)==0)&&(mindistance(j)>=mindistance(i)+a(i,j)))
mindistance(j)=mindistance(i)+a(i,j);
if a(i,j)<inf
prepoint(j)=i;
end
if mindistance(j)<=findminpointmindistance
findminpointmindistance=mindistance(j);
findminpoint=j;
end
end
end
end
end
checkedpoints(findminpoint)=