资源描述：
《实验6最短路求解--的编程实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验6最短路问题的编程实现成绩专业班级数学121学号1姓名覃绍强报告日期.实验类型：●验证性实验○综合性实验○设计性实验实验目的：熟练最短路问题的Dijkstra算法。实验内容：最短路问题的Dijkstra算法。实验原理最短路问题的Dijkstra算法：首先对图中的所有节点赋予双标号,即临时标号和永久标号,然后按一定的策略,依次判断并修改节点的临时标号,知道最后将终点改为永久标号求出最短路径。实验步骤1要求上机实验前先编写出程序代码2编辑录入程序3调试程序并记录调试过程中出现的问题及修改程序的过程4经反复调试后，运行程序并验证程序运行是否正确。5记录运行时的输入和输出。预习编
2、写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序函数文件：dijkstra.mfunction[min,path]=dijkstra(w,start,terminal)n=size(w,1);label(start)=0;f(start)=start;%初始化fori=1:nifi~=startlabel(i)=inf;endends(1)=start;u=start;whilelength(s)
3、(label(u)+w(u,v))label(v)=(label(u)+w(u,v));f(v)=u;endendend%v1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;endendifins==0v=i;ifk>label(v)k=label(v);v1=v;endendends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1;whilepath(i)~=startpath(i+1)=f(path(i));i=i+1;endpat
4、h(i)=start;L=length(path);path=path(L:-1:1);求解下图中的最短路求解过程：输入输出：>>x=0218InfInfInfInfInfInfInf20Inf61InfInfInfInfInfInf1Inf07InfInf9InfInfInfInf8670512InfInfInfInfInf1Inf503Inf21InfInfInfInfInf1304Inf6InfInfInfInf92Inf40Inf31InfInfInfInfInf2InfInf07InfInfInfInfInfInfInf637012InfInfInfInfInfIn
5、f1Inf101InfInfInfInfInfInfInfInf210>>start=1;>>terminate=11;>>[min,path]=dijkstra(x,start,terminate)min=6path=125911结果分析：即最短路径为：v1àv2àv5àv9àv11,最短距离为：16，手工计算的结果为：上述两种结果一致。总结：通过编程，将最短路的算法加深了印象，也熟悉了matlab编程，颇有收获的一次实验，给力！实验7最大流问题的编程实现成绩专业班级数学121学号8姓名秦柯柯报告日期.实验类型：●验证性实验○综合性实验○设计性实验实验目的：熟练最大流问题的
6、求解算法。实验内容：最大流问题的求解算法。实验原理：先给定初始可行流，然后找出可扩充路（增广链），调整可扩充路上的流量，使可行流增大，不断重复上述过程，直到不存在可扩充路为止。实验步骤1要求上机实验前先编写出程序代码2编辑录入程序3调试程序并记录调试过程中出现的问题及修改程序的过程4经反复调试后，运行程序并验证程序运行是否正确。5记录运行时的输入和输出。预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序使用lingo求解model:sets:point/v1,v2,v3,v4,v5/;route(point,point)/v1v2,v1v3,
7、v2v3,v2v4,v4v3,v3v5,v4v5/:transport,capacity;endsetsdata:capacity=3212042;enddatamax=z;z=@sum(point(j)
8、@in(route,@index(point,v1),j):transport(1,j));@for(point(i)
9、i#ne#@index(point,v1)#and#i#ne#@index(point,v5):@sum(point(j)
10、@in(route,i,j):transport(i,j)
