1、實驗項目：最短路徑問題實驗學時：4實驗日期：2012年11月30日實驗要求：案例模型分析實驗內容：用最短路徑模型解決具體問題前言運輸是物流過程的主要職能之一，也是物流過程各項業務的中心活動。物流過程中的其它各項活動，如包裝、裝卸搬運、物流信息等，都是圍繞著運輸而進行的?？梢哉f,在科學技術不斷進步、生產的社會化和專業化程度不斷提高的今天，一切物質產品的生產和消費都離不開運輸。物流合理化，在很大程度上取決于運輸合理化。所以，在物流過程的各項業務活動中，運輸是關鍵，起著舉足輕重的作用。而有效的縮減路徑可以使得運輸費用降低。本文運用Dijkstra算法求出最短路徑，以最大限度地節約運輸費用降低物流成本

2、，Dijkstra算法用于求解最短路徑問題最常用的方法之一。Dijkstra算法的基本步驟如下：(1)給起點Vi以P標號pvi0,其余各點均給以T標號，TVi=。(2)若Vi點為剛得到的p標號的點，考慮這樣的點為Vj,考慮Vi,Vj這條邊，且Vj為T標號，對Vj的T標號進行如下更改TVjminTVj,PVilj(3)比較所有具有T標號的點，把最小者改為P標號，即PViminVi,當存在兩個以上最小者時，可同時改為P標號，若全部點均為P標號，則停止，否則Vi代Vi改為第二步重做。案例分析下圖所示是某地區交通運輸的示意圖，試問從V1出發，經哪條路線達到V8才能使總行程最短使用Dijkstra求解。

3、步驟:V81.首先給Vi以P標號，PVi0,給其余所有的點以T標號，TV1i1,2,82.(1)考察點Vi,邊Vi,V2,Vi,V3TV2TV3minTV2,PV1minTV3,PV11213minmin,04,06(2)比較所有T標號TV2,TV3TV24最小，所以給V2以P標號,PV24,記錄路徑V1,V23.(1)V2為剛得到P標號的點，考察邊V2,V4,V2,V5TV4minTV4,PV2l24min,4TV5minTV5,PV2l25min,4(2)比較所有T標號,TV3,TV4,TV5,TV36最小，給V3以P標號,PV36，記錄路徑Vi,V34.(1)V3為剛得到P標號的點,考察

4、V3,V4,V3,V5TV4minTV4,PV3134min9,649TV5minTV5,PV3l35min8,678(2)比較所有T標號,TV4,TV5,TV58最小，給V5以P標號，令PV58，記錄路徑V2V5. (1)V5為剛得到P標號的點,考察V5,V6,V5,V7TV6minTV6,PV5l56min,8513TV7minTV7,PV5I57min,8614(2)比較所有T標號，TV4,TV6,TV7,TV49最小，給V4以P標號，令PV49,記錄路徑V2,V46. (1)V4為剛得到P標號的點,考察V4,V6,V4,V7TV6minTV6,PV4l46min13,9913TV7mi

5、nTV7,PV4I47min14,9714(2)比較所有T標號，TV6,TV7,TV613最小，給V6以P標號，令PV613,記錄路徑V5,V67. (1)V6為剛得到P標號的點，考察V6,V7,V6,V8TV7minTV7,PV6l67min14,13414TV8minTV8,PV6&min,13417(2)比較所有T標號，TV7,TV8,TV714最小，給V7以P標號,令PV714,記錄路徑V5,V78. (1)V7為剛得到P標號的點，考察V7,V8TV8minTV8,PV7l78min17,14115(2)比較所有T標號，TV815最小，給V8以P標號，令PV815,記錄路徑V7,V8實驗總結科學合理的運輸路線對物流白成本的大小影響很大。Dijkstra算法就是通過一種方法，使運輸路線最短，運費最少，盡可能的降低物流成本，提高產品的競爭力，Dijkstra,根據距V1從近到遠的順序，依次求得Vi到V8