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