郑州航空工业管理学院
物流系统规划与设计实验报告（二）
专学姓
业号名
交通运输（航空物流方向）130506208
管泽军
六年十月二十三日
二О一
f一、实验名称
实验名称：物流运输线路实验学时：6学时实验时间：20162017学年第1学期第8周周日510节实验地点：物流学院物流实验室指导教师：王永刚
二、实验目的与任务
某家运输公司签订了一项运输合同，要把A市的一批货物运送到B市。该公司根据这两个城市之间可选择的行车路线的地图，绘制了公路网络（如下图所示）。请运用运筹学模型和计算机软件，求出最短运输线路。
1
f三、实验步骤与内容
采用Dijkstra算法求解最优路线问题：算法描述如下：
1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点可能达到的长度的初值为DarcsLocateVexGvi，vi∈V；2）选择，使得DMi
Dvi∈VS；3）修改从v出发的到集合VS中任一顶点vk的最短路径长度。
算法步骤如下：
GVE1初始时令SV0TVS其余顶点，T中顶点对应的距离值若存在V0Vi，dV0Vi为V0Vi弧上的权值若不存在V0Vi，dV0Vi为∞2从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中3对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值重复上述步骤2、3，直到S中包含所有顶点，即WVi为止
2
fC程序如下：
源代码编译链接后得到可运行程序中输入
即可解题，其中10表示10个顶点、16表示16条边、12100等表示形如顶点1到顶点2之间的权值是100。
3
f四、实验结果
解得：最短运输路线为：1→4→6→9→10最短运输距离为：650五、总结分析
4
fr