dijkstra演算法鄰接矩陣

A. 最短路徑的Dijkstra演算法

Dijkstra演算法（迪傑斯特拉）是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。可以用堆優化。
Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。
其採用的是貪心法的演算法策略
大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復第2和第3步,直到OPEN表為空，或找到目標點。 #include<iostream>#include<vector>usingnamespacestd;voiddijkstra(constint&beg,//出發點constvector<vector<int>>&adjmap,//鄰接矩陣，通過傳引用避免拷貝vector<int>&dist,//出發點到各點的最短路徑長度vector<int>&path)//路徑上到達該點的前一個點//負邊被認作不聯通//福利：這個函數沒有用任何全局量，可以直接復制！{constint&NODE=adjmap.size();//用鄰接矩陣的大小傳遞頂點個數，減少參數傳遞dist.assign(NODE,-1);//初始化距離為未知path.assign(NODE,-1);//初始化路徑為未知vector<bool>flag(NODE,0);//標志數組，判斷是否處理過dist[beg]=0;//出發點到自身路徑長度為0while(1){intv=-1;//初始化為未知for(inti=0;i!=NODE;++i)if(!flag[i]&&dist[i]>=0)//尋找未被處理過且if(v<0||dist[i]<dist[v])//距離最小的點v=i;if(v<0)return;//所有聯通的點都被處理過flag[v]=1;//標記for(inti=0;i!=NODE;++i)if(adjmap[v][i]>=0)//有聯通路徑且if(dist[i]<0||dist[v]+adjmap[v][i]<dist[i])//不滿足三角不等式{dist[i]=dist[v]+adjmap[v][i];//更新path[i]=v;//記錄路徑}}}intmain(){intn_num,e_num,beg;//含義見下cout<<輸入點數、邊數、出發點：;cin>>n_num>>e_num>>beg;vector<vector<int>>adjmap(n_num,vector<int>(n_num,-1));//默認初始化鄰接矩陣for(inti=0,p,q;i!=e_num;++i){cout<<輸入第<<i+1<<條邊的起點、終點、長度（負值代表不聯通）：;cin>>p>>q;cin>>adjmap[p][q];}vector<int>dist,path;//用於接收最短路徑長度及路徑各點dijkstra(beg,adjmap,dist,path);for(inti=0;i!=n_num;++i){cout<<beg<<到<<i<<的最短距離為<<dist[i]<<，反向列印路徑：;for(intw=i;path[w]>=0;w=path[w])cout<<w<<<-;cout<<beg<<' ';}}

B. 生成樹的標准有哪些各有什麼異同

一 區別

最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。

最短路徑是從一點出發，到達目的地的路徑最小。

二 實現方法

1. 最小生成樹

2. 最小生成樹有兩種演算法來得到：Prims演算法和Kruskal演算法。

3. Kruskal演算法：根據邊的加權值以遞增的方式，一次找出加權值最低的邊來構建最小生成樹，而且規定：每次添加的邊不能造成生成樹有迴路，知道找到N-1個邊為止。

4. Prims演算法：以每次加入一個的臨界邊來建立最小生成樹，直到找到N-1個邊為止。其規則為：以開始時生成樹的集合（集合U）為起始的定點，然後找出與生成樹集合鄰接的邊（集合V）中，加權值最小的邊來建立生成樹，為了確定新加入的邊不會造成迴路，所以每一個新加入的邊，只允許有一個頂點在生成樹集合中，重復執行此步驟，直到找到N-1個邊為止。

5. 2 最短路徑

演算法描述

(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)

1． 置集合S={2,3,n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊)

2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3

3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2

Dijkstra演算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

演算法具體步驟

（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或 ∞(若u不是v的出邊鄰接點）。

（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。

（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值為頂點k的距離加上邊上的權。

（4）重復步驟（2）和（3）直到所有頂點都包含在S中。

復雜度分析

Dijkstra 演算法的時間復雜度為O(n^2)空間復雜度取決於存儲方式，鄰接矩陣為O(n^2)

C. 關於時間依賴的最短路徑演算法

Dijkstra 最短路徑演算法的一種高效率實現*

隨著計算機的普及以及地理信息科學的發展，GIS因其強大的功能得到日益廣泛和深入的應用。網路分析作為GIS最主要的功能之一，在電子導航、交通旅遊、城市規劃以及電力、通訊等各種管網、管線的布局設計中發揮了重要的作用，而網路分析中最基本最關鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量等。相應地，最短路徑問題就成為最快路徑問題、最低費用問題等。由於最短路徑問題在實際中常用於汽車導航系統以及各種應急系統等（如110報警、119火警以及醫療救護系統），這些系統一般要求計算出到出事地點的最佳路線的時間應該在1 s～3 s內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現應該是高效率的。其實,無論是距離最短、時間最快還是費用最低，它們的核心演算法都是最短路徑演算法。經典的最短路徑演算法——Dijkstra演算法是目前多數系統解決最短路徑問題採用的理論基礎，只是不同系統對Dijkstra演算法採用了不同的實現方法。
據統計，目前提出的此類最短路徑的演算法大約有17種。F.Benjamin Zhan等人對其中的15種進行了測試，結果顯示有3種效果比較好，它們分別是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，這些演算法的具體內容可以參見文獻〔1〕。其中TQQ演算法的基礎是圖增長理論，較適合於計算單源點到其他所有點間的最短距離；後兩種演算法則是基於Dijkstra的演算法，更適合於計算兩點間的最短路徑問題〔1〕。總體來說，這些演算法採用的數據結構及其實現方法由於受到當時計算機硬體發展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當的時間效率來換取空間節省。目前，空間存儲問題已不是要考慮的主要問題，因此有必要對已有的演算法重新進行考慮並進行改進，可以用空間換時間來提高最短路徑演算法的效率。
1 經典Dijkstra演算法的主要思想
Dijkstra演算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等於零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑演算法的基本過程如下：
1) 初始化。起源點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi= ;③ 標記起源點s，記k=s,其他所有點設為未標記的。
2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，並設置：
dj=min〔dj, dk+lkj〕
式中，lkj是從點k到j的直接連接距離。
3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i：
di=min〔dj, 所有未標記的點j〕
點i就被選為最短路徑中的一點，並設為已標記的。
4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：
i=j*
5) 標記點i。如果所有點已標記，則演算法完全推出，否則，記k=i，轉到2) 再繼續。
2 已有的Dijkstra演算法的實現
從上面可以看出，在按標記法實現Dijkstra演算法的過程中，核心步驟就是從未標記的點中選擇一個權值最小的弧段，即上面所述演算法的2)～5)步。這是一個循環比較的過程，如果不採用任何技巧，未標記點將以無序的形式存放在一個鏈表或數組中。那麼要選擇一個權值最小的弧段就必須把所有的點都掃描一遍，在大數據量的情況下，這無疑是一個制約計算速度的瓶頸。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊的權值進行順序排列，這樣每循環一次即可取到符合條件的點，可大大提高演算法的執行效率。另外，GIS中的數據 (如道路、管網、線路等)要進行最短路徑的計算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在GIS中稱為構建網路的拓撲關系 (由於這里的計算與面無關，所以拓撲關系中只記錄了線與結點的關系而無線與面的關系，是不完備的拓撲關系)。如果用一個矩陣來表示這個網路，不但所需空間巨大，而且效率會很低。下面主要就如何用一個簡潔高效的結構表示網的拓撲關系以及快速搜索技術的實現進行討論。
網路在數學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表〔4〕 表示，其優缺點的比較見表 1。
表 1 幾種圖的存儲結構的比較
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 稱 實現方法 優 點 缺 點 時間復雜度
鄰接矩陣 二維數組 1. 易判斷兩點間的關系 佔用空間大 O(n2+m*n)
2. 容易求得頂點的度
鄰接表 鏈表 1. 節省空間 1. 不易判斷兩點間的關系 O(n+m)或O(n*m)
2. 易得到頂點的出度 2. 不易得到頂點的入度
十字鏈表 鏈表 1. 空間要求較小 結構較復雜 同鄰接表
2.易求得頂點的出度和入度
鄰接多重表 鏈表 1. 節省空間 結構較復雜 同鄰接表
2. 易判斷兩點間的關系

目前,對於演算法中快速搜索技術的實現，主要有桶結構法、隊列法以及堆棧實現法。TQQ、DKA 以及 DKD 在這方面是比較典型的代表。TQQ雖然是基於圖增長理論的，但是快速搜索技術同樣是其演算法實現的關鍵，它用兩個FIFO的隊列實現了一個雙端隊列結構來支持搜索過程〔1〕。
DKA和DKD是採用如圖 1 所示的桶結構來支持這個運算，其演算法的命名也來源於此。在DKA演算法中，第i個桶內裝有權值落在 〔b*i, (i+1)*b) 范圍內的可供掃描的點，其中b是視網路中邊的權值分布情況而定的一個常數。每一個桶用隊列來維護，這樣每個點有可能被多次掃描，但最多次數不會超過b次。最壞情況下，DKA的時間復雜度將會是O(m*b+n(b+C/b))，其中，C為圖中邊的最大權值。DKD將點按權值的范圍大小分裝在兩個級別的桶內，高級別的桶保存權值較大的點，相應的權值較小的點都放在低級別的桶內，每次掃描都只針對低級別桶中的點。當然隨著點的插入和刪除，兩個桶內的點是需要動態調整的。在DKA演算法中，給每個桶一定的范圍以及DKD中使用雙桶，在一定程度上都是以空間換時間的做法，需要改進。

圖 1 一個桶結構的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra演算法實現
3.1 網路拓撲關系的建立
上面介紹的各種圖的存儲結構考慮了圖在理論上的各種特徵，如有向、無向、帶權、出度、入度等。而GIS中的網路一般為各種道路、管網、管線等，這些網路在具有圖理論中的基本特徵的同時，更具有自己在實際中的一些特點。首先，在GIS中大多數網路都是有向帶權圖，如道路有單雙向問題，電流、水流都有方向（如果是無向圖也可歸為有向圖的特例），且不同的方向可能有不同的權值。更重要的一點是，根據最短路徑演算法的特性可以知道，頂點的出度是個重要指標，但是其入度在演算法里則不必考慮。綜合以上4種存儲結構的優缺點， 筆者採用了兩個數組來存儲網路圖，一個用來存儲和弧段相關的數據（Net-Arc List），另一個則存儲和頂點相關的數據（Net-Node Index）。Net-Arc List用一個數組維護並且以以弧段起點的點號來順序排列，同一起點的弧段可以任意排序。這個數組類似於鄰接矩陣的壓縮存儲方式，其內容則具有鄰接多重表的特點，即一條邊以兩頂點表示。Net-Node Index則相當於一個記錄了頂點出度的索引表，通過它可以很容易地得到此頂點的出度以及與它相連的第一條弧段在弧段數組中的位置。此外，屬性數據作為GIS不可少的一部分也是必須記錄的。這樣，計算最佳路徑所需的網路信息已經完備了。在頂點已編號的情況下，建立Net-Arc List和Net-Node Index兩個表以及對Net-Arc List的排序，其時間復雜度共為O(2n+lgn)，否則為O(m+2n+lgn)。這個結構所需的空間也是必要條件下最小的，記錄了m個頂點以及n條邊的相關信息，與鄰接多重表是相同的。圖 2 是採用這個結構的示意圖。
3.2 快速搜索技術的實現
無論何種演算法，一個基本思想都是將點按權值的大小順序排列，以節省操作時間。前面已經提到過，這兩個演算法都是以時間換空間的演算法，所以在這里有必要討論存儲空間問題 (這部分空間的大小依賴於點的個數及其出度)。根據圖中頂點和邊的個數可以求出頂點的平均出度e=m/n（m為邊數，n為頂點數），這個數值代表了圖的連通程度，一般在GIS的網路圖中，e∈〔2,5〕。這樣,如果當前永久標記的點為t個，那麼，下一步需掃描點的個數就約為t～4t個。如果採用鏈表結構，按實際應用中的網路規模大小，所需的總存儲空間一般不會超過100 K。所以完全沒有必要採用以時間換空間的做法，相反以空間換時間的做法是完全可行的。在實現這部分時，筆者採用了一個FIFO隊列，相應的操作主要是插入、排序和刪除，插入和刪除的時間復雜度都是O(1)，所以關鍵問題在於選擇一個合適的排序演算法。一般可供選擇的排序演算法有快速排序、堆排序以及歸並排序等，其實現的平均時間都為O(nlgn)。經過比較實驗，筆者選擇了快速排序法。另外，Visual C++提供的run-time庫也提供了現成的快速排序的函數qsort( )可供使用。

圖 2 基於最佳路徑計算的網路拓撲表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，筆者用Visual C++實現了吉奧之星（GeoStar）中的最佳路徑模塊。以北京的街道為數據（共6 313個結點，9 214條弧段(雙向)），在主頻為133、硬碟為1 G、內存為32 M的機器上，計算一條貫穿全城、長為155.06 km的線路，約需1 s～2 s。如圖 3所示。

圖 3 GeoStar中最佳路徑實現示意圖

ps:圖片沒有辦法貼上去.
你可以參考《演算法導論》第二版