d算法matlab实验报告

实验课题目（一）：利用计算机语言编程实现D算法实验目的：本实验课程主要目的是让学生够熟练掌握图论中的D算法。实验方法：选择MATLAB语言或C语言编程实现D算法。实验要求：1.输入必要参数，包括：结点个数、节点间路径长度、给定节点；2.输出给定节点到其它各节点的最短路径、径长；3.节点间路径长度用矩阵形式表示。实验内容编译环境：matlabR2013a8.1.0.604输入参数说明：本实验使用matlab编程，主函数为main（）输入参数为：N：节点个数H：各节点的路径长度（以矩阵形式输入）a：为指定节点的索引号输出参数说明：N：为各节点到指定节点的最短距离（以长度为N的行矩阵形式表示）P：最短路径（以元胞形式表示）P1：显示每个节点最短路径的上一个节点运行界面如图：有计算结果得最短路径P和最短径长D；由图得节点v5v6v7的最短路径虽然例题答案不一致但路径长相等，也是正确的。通过计算其他例题也正确。程序流程图：在G-Gp中找到点vj，使vs到点vj的距离最小，并将vj划归到Gp以新Gp中的节点作为转接点，计算并修改（G-Gp）中的wj将vi划归到Gp中，即新的，vj与vs直连且未置定节点标值Gp={vs}ws=0设，未置定节点集；G-Gp，vj∈G-Gp，s与j直接相连vj∈G-Gp，s与j不直接相连Y重计算G-Gp中的wj的暂置值——修改wj值。中的各个节点的最短径可能经vi转接（或不转接），重新对（G-Gp）中的wj值取G-Gp选定所有w*j的最小值，并将其划归到Gp中：得到新的Gp，所有节点被置定，算法终止N附件：%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[D,P,P1]=main()%DetailedexplanationgoeshereN=input('请输入节点个数：');H=input('请输入节点间路径长度（矩阵形式）：');a=input('请输入指定节点：');%%初始化c='v1v2v3v4v5v6v7v8v9';P=cell(1,N);%用来存储最短路径的fori=1:NP{1,i}=c(2*a-1:2*a);endG=zeros(1,N);G(a)=1;D=H(a,:);D1=D;D1(a)=100;%%%在这里要记录节点p的最短路径和径长P{1,a}=c(2*a-1:2*a);%%%%%主要算法三个循环while~(sum(G)==N)n=sum(G);%n位G中1的个数[IJ]=findindex(G);fori=1:N-nd=100;forj=1:nifH(I(i),J(j))+D(J(j))d;d=H(I(i),J(j))+D(J(j));o=J(j);endendifdD(I(i));D(I(i))=d;D1(I(i))=d;%%更新距离%%%此时要记下最小路径节点序号P{1,I(i)}=[c(2*o-1:2*o)];endend[d,p]=findmin(D1);G(p)=1;D1(p)=100;end%截止这里最短路劲P中显示的是每个节点最短路径的上一个节点%%%%%%最短路径处理函数，便于显示P1=P;fori=1:Nifstr2num(P{1,i}(2))~=a;P{1,i}=[P{1,i}P{1,str2num(P{1,i}(2))}];ifstr2num(P{1,i}(4))~=aP{1,i}=[P{1,i}P{1,str2num(P{1,i}(4))}];endendendfori=1:NP{1,i}=[c(2*i-1:2*i)P{1,i}];endend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%子函数：%此函数的作用是找出输入序列中的最小值及其序号function[d,j]=findmin(B)%用于找出序列B中的最小值及其位置N=length(B);d=B(1);j=1;fori=2:N;ifdB(i);d=B(i);j=i;endendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[I,J]=findindex(B)%此函数作用是找出输入的了0,1序列中0,1的序号并输出I=[];J=[];fori=1:length(B)ifB(i)==0I=[Ii];elseJ=[Ji];endend