运筹学上机实验报告单
20 14 －20 15 学年第 2 学期
实验名称 最短路问题的计算机求解 日期：2015 年 5 月 26 日
班级 姓名 学号
实验
目的 掌握最短路问题的计算机求解方法。
实验
内容 （1）最短路问题的lingo编程与计算机求解步骤。
（2）最短路问题计算机求解的输出结果分析。
操作
步骤 （1）进入运筹学软件。
（2）利用相应例题（P143例5-1）熟悉网络最短路问题的计算机求解步骤。
（3）对求解中出现问题所进行内容在同学间相互交流，并进行总结。
（4）完成上机作业（P162习题3），并记录步骤与结果。
结果
显示
与
分析 习题3结果：
Variable Value
U( 1) 0.000000
U( 2) -5.000000
U( 3) -2.000000
U( 4) 3.0000
U( 5) 2.000000
U( 6) -11.00000
U( 7) -7.000000
W( 1, 2) 4.000000
W( 1, 3) -2.000000
W( 1, 4) 3.000000
W( 1, 5) 5.000000
W( 2, 6) 1.000000
W( 3, 2) 7.000000
解：1.给起点标以v1（0，s）
2. I={v1}， J={v2，v3，v4，v5，v6，v7}
弧集合{（vi，vj）| vi I，vj J }={（v1，v2），（v1，v3），（v1，v4）}
并有：s12=l1+c12=0+2=2
s13=l1+c13=0+5=5
s14=l1+c14=0+3=3
min(s12,s13,s14)=s12=2
给弧（v1,v2）的终点v2标以（2，1）
3.此时I={v1,v2} J={v3,v4,v5,v6,v7}弧集合{（vi，vj）| vi I，vj J }={(v1,v3)(v1,v4)(v2,v3)}
并有：s23=l2+c23=2+2=4
min(s13,s14,s23)=s14=3
此时，给弧（v1,v4）的终点v4标以（3，1）
4. 此时I={v1,v2,v4} J={v3,v5,v6,v7}
弧集合{（vi,vj）| vi I,vj J }
={(v1,v3),( v2,v3),( v2,v6),( v4,v3),( v4,v5) }
并有：s26=l2+c26=2+7=9
s43=l4+c43=3+1=4
s45=l4+c45=3+5=8
min(s13,s23 ,s26,s43,s45)=s23=s43=4
此时，给弧（v2,v3）的终点v3标以（4，2）
给弧（v4,v3）的终点v3标以（4，4） 5.此时I={v1,v2,v3,v4 } J={ v5,v6,v7 }
弧集合{（vi，vj）| vi I，vj J }=
{ ( v2,v6),( v3,v6),( v3,v5),( v4,v5) }
并有：s36=l3+c36=4+5=9
s35=l3+c35=4+3=7
【转】彻底弄懂最短路径问题（图论）
P.S.根据个⼈需要，我删改了不少
问题引⼊
问题：从某顶点出发，沿图的边到达另⼀顶点所经过的路径中，各边上权值之和最⼩的⼀条路径——最短路径。解决最短路的问题有以下算
法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出⼀篇，其中Floyd算法可以求
解任意两点间的最短路径的长度。笔者认为任意⼀个最短路算法都是基于这样⼀个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是
直接从A到B，2是从A经过若⼲个节点到B。
⼀.Dijkstra算法
该算法在《数据结构》课本⾥是以贪⼼的形式讲解的，不过在《运筹学》教材⾥被编排在动态规划章节，建议读者两篇都看看。
(1) 迪杰斯特拉(Dijkstra)算法按路径长度递增次序产⽣最短路径。先把V分成两组：
S：已求出最短路径的顶点的集合
V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加⼊到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶
点到Vk的路径权值之和（反证法可证）。
(2) 求最短路径步骤
1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值， 若存在，为弧上的权值（和SPFA初始化⽅式不同），若不存在
，为Inf。
2. 从T中选取⼀个其距离值为最⼩的顶点W(贪⼼体现在此处)，加⼊S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作⽤⾄关重
要)，对T中顶点的距离值进⾏修改：若加进W作中间顶点，从V0到Vi的距离值⽐不加W的路径要短，则修改此距离值（上⾯两个并列for循环，
使⽤最⼩点更新）。
3. 重复上述步骤，直到S中包含所有顶点，即S=V为⽌（说明最外层是除起点外的遍历）。
(3) 问题：Dijkstar能否处理负权边？（来⾃《图论》）
答案是不能，这与贪⼼选择性质有关，每次都找⼀个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径；但如果存在负
Microsoft Excel 11.0 运算结果报告
工作表 [20103848李园园.xls]Sheet1
报告的建立: 2003-1-19 6:23:54目标单元格 (最小值)单元格名字初值终值
$E$13V7010
可变单元格单元格名字初值终值$D$2V2 路径00$D$3V5 路径01$D$4V7 路径00$D$5V5 路径00
$D$6V2 路径00
$D$7V6 路径00
$D$8V3 路径00
$D$9V8 路径00
$D$10V6 路径01
$D$11V8 路径01
$D$12V5 路径00
$D$13V7 路径00
约束单元格名字单元格值公式状态型数值
$G$2V1 网络流1$G$2>=$H$2到达限制值0
$G$3V2 网络流0$G$3=$H$3未到限制值0
$G$4V3 网络流0$G$4=$H$4未到限制值0
$G$5V4 网络流0$G$5=$H$5未到限制值0
$G$6V5 网络流0$G$6=$H$6未到限制值0
$G$7V6 网络流0$G$7=$H$7未到限制值0
$G$8V7 网络流0$G$8=$H$8未到限制值0
$D$2V2 路径0$D$2=二进制到达限制值0
$D$3V5 路径1$D$3=二进制到达限制值0
$D$4V7 路径0$D$4=二进制到达限制值0
$D$5V5 路径0$D$5=二进制到达限制值0
$D$6V2 路径0$D$6=二进制到达限制值0
$D$7V6 路径0$D$7=二进制到达限制值0
$D$8V3 路径0$D$8=二进制到达限制值0
$D$9V8 路径0$D$9=二进制到达限制值0
$D$10V6 路径1$D$10=二进制到达限制值0
$D$11V8 路径1$D$11=二进制到达限制值0
$D$12V5 路径0$D$12=二进制到达限制值0
$D$13V7 路径0$D$13=二进制到达限制值0
