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

2、物流成本，Dijkstra算法用于求解最短路徑問題最常用的方法之一。Dijkstra算法的基本步驟如下：（1） 給起點以P標號,其余各點均給以T標號， 。（2） 若點為剛得到的標號的點，考慮這樣的點為，考慮這條邊，且為T標號，對的T標號進行如下更改 （3）比較所有具有標號的點，把最小者改為標號，即，當存在兩個以上最小者時，可同時改為標號，若全部點均為標號，則停止，否則代改為第二步重做。 案例分析下圖所示是某地區(qū)交通運輸?shù)氖疽鈭D，試問從出發(fā)，經(jīng)哪條路線達到才能使總行程最短？使用Dijkstra求解。 5 9 4 4 7 5 4 6 4 5 1 7 6 步驟：1. 首先給以P標號，,給其余所有的點

3、以T標號，2. （1）考察點，邊 （2)比較所有T標號，最小，所以給以P標號，令,記錄路徑3. (1) 為剛得到P標號的點，考察邊 （2）比較所有T標號，,最小，給以P標號，令,記錄路徑 4. （1）為剛得到P標號的點，考察 （2）比較所有T標號，,最小，給以P標號，令 ,記錄路徑 5. （1) 為剛得到P標號的點，考察 （2）比較所有T標號，,最小,給以P標號,令，記錄路徑6. （1）為剛得到P標號的點，考察 (2) 比較所有T標號,最小,給以P標號,令,記錄路徑 7. （1）為剛得到P標號的點，考察 (2)比較所有T標號，,最小,給以P標號,令,記錄路徑 8. （1）為剛得到P標號的點，考察 （2）比較所有T標號，最小，給以P標號,令,記錄路徑 至此可以得到最短路徑為,最短行程為15 實驗總結 科學合理的運輸路線對物流的成本的大小影響很大。Dijkstra算法就是通過一種方法，使運輸路線最短，運費最少，盡可能的降低物流成本，提高產(chǎn)品的競爭力，Dijkstra，根據(jù)距從近到遠的順序，