求解最優(yōu)交通路徑

1、求解最優(yōu)交通路徑C程 序 設 計求解最優(yōu)交通路徑求解最優(yōu)交通路徑在程序中預置部分城市間的距離，然后由用戶選擇兩個城市，計算出兩城市之間的最短距離以及相應的路線。CONTENTS01編程思路分析基礎知識點具體實現(xiàn)總結(jié)030204編程思路分析1.編程思路分析定義CreateUDN() 函數(shù)，根據(jù)用戶輸入的頂點數(shù)和邊數(shù)生成一個相應的交通圖，其中頂點對應于城市，邊對應于城市間的直接通路。定義narrate() 函數(shù)輸出能夠進行計算的城市列表。定義函數(shù)ShortestPath() 計算城市間的最短路徑。定義函數(shù)output()用于輸出城市間的最短路徑。在主函數(shù)中調(diào)用以上各函數(shù)以實現(xiàn)程序功能。基礎知識點圖

2、(Graph)是一種比線性表和樹更為復雜的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)：研究數(shù)據(jù)元素之間的一對一關(guān)系，在這種結(jié)構(gòu)中，除第一個和最后一個元素外，任何一個元素都有唯一的直接前驅(qū)和直接后繼。圖結(jié)構(gòu)：研究數(shù)據(jù)元素之間的多對多關(guān)系，在這種結(jié)構(gòu)中，任意兩個元素之間可能存在關(guān)系，即結(jié)點之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。圖：記為 G( V, E ) 其中：V是G的頂點集合，是有窮非空集； E是G的邊集合，是有窮集。V=vertex E=edge2.基礎知識點有向圖：圖G中的每條邊都是有方向的。無向圖：圖G中的每條邊都是無方向的。G2=(V2,E2)V2=A, B, C, D, E,FE2 =(A, B

3、), (A, E),(B, E), (B, F), (C, D), (C, F), (D, F)G1 = (V1, E1)V1=A, B, C, D, EE1=, , , , , , BCAFEDG2:G1:EACBD2.基礎知識點圖的鄰接矩陣表示：BACDFEAij=0 (i,j)E1 (i,j)E定義: 矩陣的元素為ABCDEFABCDEF0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 無向圖：2.基礎知識點對稱矩陣ABECD有向圖:0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1

4、 1 0 0 0 0 0 1 0 0 ABCDE圖的鄰接矩陣表示：ABCDE2.基礎知識點非對稱矩陣帶權(quán)圖（網(wǎng)）的鄰接矩陣表示：以有向網(wǎng)為例：Aij= (i,j)Ewij (i,j)E定義: 矩陣的元素為AABCDEABECD20152518101020BCED2.基礎知識點2.基礎知識點 Dijkstra(迪杰斯特拉)算法Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。算法思想：設G=(V,E)是一個帶權(quán)圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始

5、時S中只有一個源點，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。2.基礎知識點 Dijkstra(迪杰斯特拉)算法算法步驟：（1）初始時，S只包含源點，即Sv，v的距離為0。U包含除v外的其他頂點，即:U=其余頂點，若v與U中頂點u有邊，則正常有權(quán)值，若u不是v的出邊鄰接點，則權(quán)值為。（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距

6、離就是v到k的最短路徑長度）。（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。（4）重復步驟（2）和（3）直到所有頂點都包含在S中。具體實現(xiàn)總結(jié)4.總結(jié)本例中，用圖表示城市交通網(wǎng)絡。圖的一般形式記為 G( V, E )，其中：V是G的頂點集合，E是G的邊集合。根據(jù)圖的每條邊是否有方向可將圖分為有向圖和無向圖，有向圖和無向圖均可用鄰接矩陣來表示。若圖中每條邊均帶有權(quán)重，則為帶權(quán)圖。本例中的城市交通網(wǎng)絡圖就是一個帶權(quán)圖，權(quán)重為兩城市之間的距離。Dijkstra(迪杰斯特拉)算法是典型的最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最