物流系统规划与设计实验报告2

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