資源描述：
《excel 求解最短路徑問題》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、Excel求解最短路徑問題金曉龍（廣東女子職業(yè)技術學院藝信系,廣東廣州511450）摘要：許多實際應用問題都與最短路徑相關，解決最短路徑問題通常采用圖論與計算機技術結合的方法，本文使用Excel的工作表和自定義宏函數(shù)，采用Dijkstra算法和鏈表動態(tài)數(shù)據(jù)結構解決最短路徑問題，并在Excel的VBA環(huán)境編程運行。關鍵詞：Excel最短路徑鏈表Dijkstra算法中圖分類號：TP311ExcelSolutionofShortestPathProblemJinXiaolong（GuangdongWomen’sPolytechnicCollege,Arta
2、ndInformationDepartment,Guangzhou511450,China）Abstract：Manypracticalapplicationproblemsarerelatedtotheshortestpathproblem.Themethodcombinedgraphtheorywithcomputertechnologyisusuallyadoptedtosolvetheshortestpathproblem.ThisarticledescribeshowtosolvetheshortestpathproblembyusingE
3、xcelworksheetandcustommacrofunctions,Dijkstraalgorithmandlinkedlistofdynamicdatastructure.Finally,allisprovedbyprogrammingandrunninginExcelVBA.Keywords：Excel；shortestpasth；dynamicarray；Dijkstraalgorithm1引言在實際應用中，許多問題都與最短路徑有關，如：物流路徑、交通導航、網絡路由、電力傳輸、綜合布線等，而且最短路徑還可抽象為許多其它的實際問題，如：最小
4、費用、最短時間、最小負載、最少人員等，解決最短路徑問題通常采用圖論與計算機技術結合的方法。圖論是數(shù)學的一個分支，它以圖為研究對象，研究頂點和邊組成的圖形的數(shù)學理論和方法。Dijkstra算法是一種經典的求最短路徑算法，它采用標號法反復掃描網絡的節(jié)點，尋找出最佳路徑。本文采用Dijkstra算法與鏈表數(shù)據(jù)結構相結合，在Excel的VBA中編程實現(xiàn)最短路徑搜索。Excel是應用廣泛的電子表格軟件，在其自帶的VBA環(huán)境里而非專門的編程環(huán)境里解決最短路徑問題，更具有一定的實際意義。由于在VBA中不能顯式使用指針，采用類實現(xiàn)鏈表數(shù)據(jù)結構。2最短路徑問題給定一個
5、賦權的拓撲圖D=(V，A)，V為頂點集，A為邊集，記D中每一條弧aij=(vi，vj)上的權為wij(aij)=wij。給定D中一個起點vs和vt終點，設P是D中從vs到vt的一條路，則定義路P的權是P中所有弧的權之和，記為w(P)，即：w(P)=∑wij。又若P1是D圖中vs到vt的一條路，且滿足w(P1)=min{w(P)}，式中對D的所有從vs到vt的路P取最小，則稱P1為從vs到vt的最短路徑，w(P1)為從vs到vt的最短距離。3最短路徑算法最短路徑算法有多種，Dijkstra、Floyd、Kruskal等算法，其中Dijkstra是最常用
6、的求最短路徑的算法。Dijkstra算法核心思想就是采用逐節(jié)點擴展的方式，確定各節(jié)點到起始點的最短距離。采用標號法搜索各頂點，標號的目的就是區(qū)分該頂點是否已處理過。將頂點分為兩個頂點集，第一個為已處理頂點集B，第二個為未處理頂點集C，開始時B中只包括起始點vs，C中包括除起始點外的所有網絡節(jié)點。確定各頂點vi的D(vi)值，D(vi)值為已探索到vi到起始點vs的最小值，隨著搜索的不斷進行，D(vi)會發(fā)生變化。搜索開始時，D(vs)=0，與起始點相連的D(vi)為支路權值，不與起始點相連的D(vi)為+∞，然后，從C中選一個D(vi)最小的節(jié)點，修
7、改與之相連的各節(jié)點的D(vi)值，將該節(jié)點從C中移到B中，記錄下被修改節(jié)點的前一節(jié)點信息，重復前面過程，直到所有的頂點均搜索。Dijkstra算法的具體步驟：①給vs以P標號，D(vs)=0，其余的各點為T標號（P標號表示節(jié)點在B集，T標號表示節(jié)點在C集），T(vi)=+∞；②若vi為剛得到P標號的點，選擇T標號點vj，進行修改:D(vj)=min{D(vj),D(vi)+wij}，記錄vi與vj關系；(wij為節(jié)點i、j支路權值)③在C集中選擇D(vi)最小的節(jié)點vi，給vi以P標號重復②直到處理完所有節(jié)點；④搜索完時，所有節(jié)點的D值已確定，對應所
8、求終點D值及前后節(jié)點關系可找到最短路徑。4路徑圖描述及鏈表結構求圖1中節(jié)點間的最短路徑。5圖1帶權無向圖10
