运输网络线路优化计算题.ppt

最短路径算法1、采用Dijkstra算法基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号），或者是从vs到该点的最短路的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，直至求出从vs到各点的最短路。2、应用结论：如果P是D中从vs到vj的最短路，vi是中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。3、各路径上权值wij≥0例题237184566134105275934682求从1到8的最短路径X={1},w1=0237184566134105275934682min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},w4=1w4=1w1=04237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},w2=2w1=0w4=1w2=2X={1,2,4}237184566134105275934682min{c16,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},w6=3w2=2w4=1w1=0w6=3237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},w7=3w2=2w4=1w1=0w6=3w7=3237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},w5=6w2=2w4=1w1=0w6=3w7=3w5=6237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+8}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10237184566134105275934682X={1,2,3,4,5,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第一题第二题第三题选择题作业1运输问题的合理优化1.（）是在一般货物运价的基础上，加上或减去一定的百分比后公布的，适用于指定地区内少数货物的运输。A.整箱货运价B.特种货物运价C.货物等级运价D.一般货物运价2.在综合运输体系中，（）是实现运输的基础。A.一体化的运输系统B.多元化的运输系统C.交通实体网络系统D.交通基础网络系统3.国际多式联运通常是以（）为运输单元的。集装箱B.卡车C.火车D.轮船4.在国际多式联运的运输组织形式中，其中是主要组织形式的是（）。A.海陆联运B.陆陆联运C.陆桥运输D.海空联运5.在国际多式联运的运输组织形式中，（）又称为空桥运输。A.海陆联运B.陆陆联运C.陆桥运输D.海空