14天閱讀挑戰賽

目錄

1.問題描述

2.問題分析

3.算法設計

4.C++程序

5.算法分析

---

1.問題描述

? ? ? ? 對于有向帶權圖G=(V,E)，其中每條邊的權值都是非負實數。給定V中的一個節點（稱為源點），計算源點到其他各節點之間的最短路徑，即單源最短路徑。

2.問題分析

????????Dijkstra算法是解決單源最短路徑問題的貪心算法。Dijkstra算法基本思路是先求出源點離當前節點最短的一條路徑，然后根據當前最短路徑末端點能夠到達的點求出下一條離源點最近的路徑，直到求出源點到其他各節點的最短路徑。

3.算法設計

????????將節點集合V劃分為兩部分——集合S和V-S（節點總的集合減去已經確定最短路徑的點的集合）。其中，集合S中的節點到源點的最短路徑已經確定，集合S中的節點到源點的最短路徑已經確定，集合V-S中節點的路徑稱為特殊路徑，數組dist[]用于記錄從源點到每個節點的最短特殊路徑的長度。Dijkstra算法的貪心策略是選擇最短的特殊路徑長度dist[t]，將節點t添加到集合S中，同時借助節點t更新dist[]。一旦集合S包含了所有的節點，dist[]就是從源點到其他節點的最短路徑長度。

具體步驟如下：

1）確定合適的數據結構。用鄰接矩陣(二維數組G[][])存儲圖，用一維數組dist[i]記錄從源點到節點i的最短路徑長度，用一維數組p[i]記錄最短路徑上節點的直接前驅，例如p[2]=3，則2的前一個節點為3；

2）初始化。假設節點u為源點，令集合S={u}，對于集合V-S中的節點i，初始化dist[i]=G[u][i]。入股從源點u到節點有邊相連，就初始化p[i]=u，否則初始化p[i]=-1；

3）找最小。根據貪心策略查找集合V-S中dist[]最小的節點t，t就是集合V-S中距離源點u最近的節點，將節點t添加到集合S中；

4）執行松弛操作。對于集合V-S中的所有節點j，檢查是否可以借助節點t得到更短的路徑。如果源點u經節點t到節點j的路徑更短（即：dist[j]>dist[t]+G[t][j]），則更新dist[j]=dist[t]+G[t][j]（即執行松弛操作）并記錄j的直接前驅為t（即p[j]=t）。

5）重復步驟3和4，直到集合V-S為空。由此可以得到源點u到其他各節點的最短路徑長度，此位還可以通過前驅數組p[]逆向找到最短路徑上經過的點。

4.C++程序

//program 2.5.0 dijkstra算法 #include<iostream> #include<algorithm> #include<stack> using namespace std; const int N = 1005; const int INF = 0x3f3f3f3f; //無窮大 int G[N][N], dist[N]; //G[][]為鄰接矩陣，dist[i]表示源點到結點i的最短路徑長度 int p[N]; //p[i]表示源點到結點i的最短路徑上i的前驅 int n, m; //n為結點數，m為邊數 bool flag[N]; //如果flag[i]等于true，說明結點i已經加入到S集合;否則i屬于V-S集合void dijkstra(int u) {for (int i = 1; i <= n; i++) { //初始化dist[i] = G[u][i]; //初始化源點u到其他各個結點的最短路徑長度flag[i] = false;if (dist[i] == INF)p[i] = -1; //源點u到該結點的路徑長度為無窮大，說明源點u與結點i不相鄰elsep[i] = u; //說明結點i與源點u相鄰，設置i的前驅為u}dist[u] = 0;flag[u] = true; //初始時，集合S中只有源點ufor (int i = 1; i < n; i++) {int temp = INF, t = u;for (int j = 1; j <= n; j++) { //在集合V-S中尋找距離源點u最近的結點tif (!flag[j] && dist[j] < temp) {t = j;temp = dist[j];} }if (t == u) return; //找不到t，跳出循環flag[t] = true; //否則，將t加入S集合for (int j = 1; j <= n; j++) { //更新t的鄰接點j的最短路徑長度，松弛操作 if (!flag[j] && dist[j] > dist[t] + G[t][j]) {dist[j] = dist[t] + G[t][j];p[j] = t;}}} }void findpath(int u){//輸出源點到其它各結點的路徑 int x;stack<int>s;cout<<"源點為："<<u<<endl;for(int i=1;i<=n;i++){x=p[i];while(x!=-1){s.push(x);x=p[x];}cout<<"源點到其它各結點最短路徑為：";while(!s.empty()){cout<<s.top()<<"--";s.pop();}cout<<i<<";最短距離為："<<dist[i]<<endl;} }int main() {int u, v, w, st;//u、v表示結點，w表示u--v的距離，st表示源點int t;//測試用例數 cin >> t;while (t--) {cin >> n >> m; //n為節點個數，m為兩點直接有相連權值的個數for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)G[i][j] = INF;//初始化鄰接矩陣為無窮大while (m--) {cin >> u >> v >> w;G[u][v] = min(G[u][v], w); //鄰接矩陣儲存，保留最小的距離}cin >> st;//輸入源點 dijkstra(st);for (int i = 1; i <= n; i++) {//輸出源點到各結點的最短路徑長度，即dist[]數組 if (i != 1) cout << " ";if (dist[i] == INF)cout << "impossible";elsecout << dist[i];}cout << endl;findpath(st);}system("pause");return 0; }

5.算法分析

1）算法復雜度：找最小以及松弛操作本身執行了n次，需要重復n-1，總的執行次數均為次，時間復雜度為O()。

2）空間復雜度：輔助數組flag[]、p[]以及變量i、j、t、temp等，空間復雜度為O(n)。

?

總結

以上是生活随笔為你收集整理的贪心算法——Dijkstra最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。