《运筹学最短路例解题步骤》由会员分享，可在线阅读，更多相关《运筹学最短路例解题步骤（2页珍藏版）》请在金锄头文库上搜索。
1、解：解：1.给给起点起点标标以以 v1（ （0， ，s） ）2. I=v1， ， J=v2， ，v3， ，v4， ，v5， ，v6， ，v7弧集合弧集合（ （vi， ，vj） ）| v viI，v vj J =（ （v1， ，v2），）， （ （v1， ，v3），），（ （v1， ，v4） ） 并有：并有：s12=l1+c12=0+2=2s13=l1+c13=0+5=5s14=l1+c14=0+3=3min(s12,s13,s14)=s12=2给给弧（弧（v1,v2）的）的终终点点 v2标标以（以（2， ，1） ）3.此此时时 I=v1,v2 J=v3,v4,v5,v6,v7弧集合弧集合（ （
2、vi， ，vj） ）| v viI，v vj J =(v1,v3)(v1,v4)(v2,v3)并有：并有：s23=l2+c23=2+2=4min(s13,s14,s23)=s14=3此此时时， ，给给弧（弧（v1,v4）的）的终终点点 v4标标以（以（3， ，1） ）4. 此此时时 I=v1,v2,v4 J=v3,v5,v6,v7弧集合弧集合（ （vi,vj） ）| v viI,v vj J =(v1,v3),( v2,v3),( v2,v6),( v4,v3),( v4,v5) 并有：并有：s26=l2+c26=2+7=9s43=l4+c43=3+1=4s45=l4+c45=3+5=8min
3、(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） ）| v viI，v vj J = ( v2,v6),( v3,v6),( v3,v5),( v4,v5) 并有：并有：s36=l3+c36=4+5=9s35=l3+c35=4+3=7min(s26,s36 ,s35,s45 )=s35=7此此时时， ，给给弧（弧（v3,v5
4、）的）的终终点点 v5标标以（以（7， ，3） ）6. 此此时时 I=v1,v2,v3,v4 ,v5 J= v6,v7 弧集合弧集合（ （vi， ，vj） ）| v viI，v vj J = ( v2,v6),( v3,v6),( v5,v6) 并有：并有：s56=l5+c56=7+1=8min(s26,s36 ,s56 )=s56=8此此时时， ，给给弧（弧（v5,v6）的）的终终点点 v6标标以（以（8， ，5） ）7. 此此时时 I=v1,v2,v3,v4 ,v5, v6 J= v7 弧集合弧集合（ （vi， ，vj） ）| v viI，v vj J = ( v6,v7) 并有：并有：s67=l6+c67=8+5=13 此此时时最短路径最短路径为为： ：v1v2v3v5v6v7或或 v1v4v3v5v6v7距离距离为为： ：13
