Dijkstra算法在求解物流运输最短路径中的应用

ValueEngineeringNo.5,2009200950，。，、、，。，、，。，。，，，。，，，。1，、。，，。，，；，、、、，，。，，，“”，（），、、。：（1），。，，，DijkstraToApplyonDijkstraAlgorithminSolvingtheShortestPathofLogisticsTransportingWangHaixiao（，400715）（SouthwestUniversity，Chongqing400715，China）：，。。，Dijkstra，，，，。Abstract:Transportisnotonlyoneofthemainfunctions,butalsothecenterofbusinessactivitiesinthelogisticprocess.Thisarticleintroducestheimportanceoftransportinlogisticsatfirst.Then,elaboratesthebasicideaoftheDijkstraalgorithmandchoosestheshortestpathoftransportintheapplication,toachievetheshortestpath,minimumfreightandmaximizethecost-savinginlogistictransport.Itistoenhancethecompetitivenessofproducts.：；；Dijkstra；Keywords:logistics；transport；Dijkstraalgorithm；path：TP301·6;F252：A：1006-4311（2009）05-0082-03———————————————————————：（1982-），，，，。SupplyChainRisk[C].AshgatePublishingLimited,2004.[2]、：《》[M]；，2007:21-45。[3]HallikasaJ,Veil-MattiV,MarkkuT.Riskanalysisandassessmentinnetworkenvironments[J].InternationalJournalofProductionEconomics,2002,78(1):45-55.[4]、：《》[J]；《》2004（3）:66-71。[5]AvenT,VinnemJE,WienckeHS.Adecisionframeworkforriskmanagement,withapplicationtotheoffshoreoilandgasindustry[J].ReliabilityEngineeringandSystemSafety,2007,92(4):433-448.[6]BogatajD,BogatajM.Measuringthesupplychainriskandvulnerabilityinfrequencyspace[J].InternationalJournalofProductionEconomics,2007,108(1-2):291-301.!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!doi：10.3969/j.issn.1006-4311.2009.05.028-82-ValueEngineeringNo.5,200920095。，，。，，，，[1]。（2）。，：、、、。，。，，，16％，26％，8％，44％，6％，9％～10％，。，，，，。，，，，，，。，。，，，，。22.1①。，，，。②，、、、。，“”[2]。，，，，“”。，，，，。③，、、、，，。，，，，，，，。2.2①。，，，。，，，，，。②。，、、、、，，[3]。③。，，。，，，。3Dijkstra（Dijkstra）（，）（）（）。———，，n，，，，[4]。，。Dijkstra：（1）V1（0，S）。（2）I，J{（Vi，Vj）|Vi∈I，Vj∈J}。，。（3），。Vt（Lt，Kt），VsVtLt，VsVt，KtVs-83-ValueEngineeringNo.5,200920095。Vt，VsVt。，。（4），Sij=Li+Cij（1）。Sij，，（Vc,Vd）.（Scd，C），2。，Sij，，，，，。4Dijkstra，，。1。V1，V2，…，V77，V1，V7，（），（）。Dijkstra，，（1）V1（0，S）。（2）I={V1}；J={V2，V3，V4，V5，V6，V7}。{[Vi，Vj]│Vi，VjI，J}={[V1，V2]，[V1，V3]}，：S12=L1+C12=0+15=15；S13=L1+C13=0+10=10；Min（S12，S13）=S13=10。[V1，V3]V3（10，1）V1V310，V1V3V3V1。（3），I={V1，V3}；J={V2，V4，V5，V6，V7}。{[Vi，Vj]│Vi，VjI，J}={[V1，V2]，[V3，V2]，[V3，V5]}，：S32=L3+C32=10+3=13；S35=L3+C35=10+4=14；Min（S12，S32，S35）=S32=13。[V3，V2]V2（13，3）。（4），I={V1，V3，V2}；J={V4，V5，V6，V7}。{[Vi，Vj]│Vi，VjI，J}={[V3，V5]，[V2，V4]，[V2，V7]}，：S24=L2+C24=13+6=19；S27=L2+C27=13+17=30；Min（S35，S24，S27）=S35=14。[V3，V5]V5（14，3）。（5），I={V1，V2，V3，V5}；J={V4，V6，V7}。{[Vi，Vj]│Vi，VjI，J}={[V2，V4]，[V5，V4]，[V2，V7]，[V5,V6]}，：S54=L5+C54=14+4=18；S56=L5+C56=14+2=16；Min（S24，S54，S27，S56）=S56=16。[V5，V6]V6（16，5）。（6），I={V1，V2，V3，V5，V6}；J={V4，V7}。{[Vi，Vj]│Vi，VjI，J}={[V2，V4]，[V5，V4]，[V2，V7]，[V6，V7]}，：S67=L6+C67=16+6=22；Min（S24，S54，S27，S67）=S54=18。[V5，V4]V4（18，5）。（7），I={V1，V2，V3，V4，V5，V6}；J={V7}。{[Vi，Vj]│Vi，VjI，J}={[V2，V7]，[V4，V7]，[V6，V7]}，：S47=L4+C47=18+5=23；Min（S27，S47，S67）=S67=22。[V6，V7]V7（22，6）。（8），I={V1，V2，V3，V4，V5，V6，V7}；J=Φ。{[Vi，Vj]│Vi，VjI，J}=Φ；。（8）。V7（22，6），V1V722，V7V6，V6（16，5）V6V5，V5（14，3）V5V3，V3（10，1）V3V1，V1→V3→V5→V6→V7，22。，Dijkstra，，。———————————————————————：[1]：《》[M]；，2002：56。[2]：《》[M]；，1995：34。[3]、：《》[M]；，2007：98。[4]：《》[M]；，2000：207。-84-