




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、 單源最短路徑的Dijkstra算法: 問題描述: 給定一個帶權有向圖G=(V,E),其中每條邊的權是非負實數。另外,還給定V中的一個頂點,稱為源。現在要計算從源到所有其他各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。算法描述: Dijkstra算法是解單源最短路徑的一個貪心算法。基本思想是:設置頂點集合S并不斷地做貪心選擇來擴充這個集合。一個頂點屬于S當且僅當從源到該頂點的最短路徑長度已知。初始時,S中僅含有源。設u是G的某一個頂點,把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑,并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。Di
2、jkstra算法每次從V-S中取出具有最短特殊路長度的頂點u,將u添加到S中,同時對數組dist做必要的修改。一旦S包含了所有V中頂點,dist就記錄了從源到所有其他頂點之間的最短路徑長度。源代碼:#include <iostream> #define MAX 1000#define LEN 100int k=0, bLEN;using namespace std;/-數據聲明-/cij表示邊 (i,j)的權/disti表示當前從源到頂點i的最短特殊路徑長度/previ記錄從源到頂點i的最短路徑上的i的前一個頂點/-void Dijkstra(int n, int v, int d
3、ist, int prev, int cLEN)bool sLEN;/ 判斷是否已存入該點到S集合中for (int i = 1; i <= n; i+)disti = cvi;si = false;/初始都未用過該點if (disti = MAX)previ = 0;/表示v到i前一頂點不存在elseprevi = v;distv = 0;sv = true;for (int i = 1; i < n; i+)int temp = MAX;int u = v;for (int j = 1; j <= n; j+)if (!sj) && (distj <
4、 temp) /j不在s中,v到j距離不在為無窮大u = j; / u保存當前鄰接點中距離最小的點的號碼temp = distj;su = true;k+;bk = u;cout << "-" << endl;cout << "迭代次數:" << i << endl;cout << "頂點為:"cout << v << "t"for (int i = 1; i <= k; i+)cout << bi &
5、lt;< "t"cout << endl;for (int j = 1; j <= n; j+)if (!sj) && cuj < MAX)int newdist = distu + cuj;if (newdist < distj)distj = newdist;/更新distprevj = u;/記錄前驅頂點cout << "單源路徑分別為:" << endl;for (int i = 2; i <= n; i+)if (disti != MAX)cout <<
6、; disti << " "cout << endl; cout << "-" << endl;/for (int i = 1; i <= n; i+)/ti = previ;int pLEN;for (int i = 2; i <= n; i+)cout << "dist" << i << "=" << disti << " "cout << "路徑為:
7、" << v << "t"/*while (ti != v)cout << ti << "t"ti = prevti;*/int m = previ;int k=0;while (m != v)k+;pk = m;m = prevm;for (int x = k; x >= 1; x-)cout << px << "t"cout << i;cout << endl;int main()int i, j,k, m,n, v=1
8、;int distLEN, prevLEN, cLENLEN;cout << "請輸入頂點個數:" << endl;cin >> n;cout << "請輸入邊的個數:" << endl;cin >> m;for (i = 1; i <= n; i+)for (j = 1; j <= n; j+)if (i = j)cij = 0;elsecij = MAX;cout << "請輸入每條邊的權_格式為: i j 權" << endl;for (k = 1; k <= m; k+)cin >> i;cin >> j;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 網絡攻擊手段演變-洞察闡釋
- 自動駕駛產業鏈分析-洞察闡釋
- 慢病管理平臺評估-洞察及研究
- 大數據資源共享平臺-洞察闡釋
- 知識產權轉讓中的風險管理與策略-洞察闡釋
- 表情包在不同文化中的適應性分析-洞察闡釋
- 軌交系統集成創新-洞察闡釋
- 網絡切片驅動的NFV功能虛擬化創新架構研究-洞察闡釋
- 農業大數據與智能金融服務創新-洞察闡釋
- 橈動靜脈瘺的護理查房
- 通信線路工程施工組織設計方案【實用文檔】doc
- 護士注冊健康體檢表下載【可直接打印版本】
- 預計財務報表編制及分析課件
- 骨科出科試題帶答案
- 河道基槽土方開挖專項施工方案
- Q∕SY 1347-2010 石油化工蒸汽透平式壓縮機組節能監測方法
- 現代美國玉米商業育種的種質基礎概要
- GB∕T 4162-2022 鍛軋鋼棒超聲檢測方法
- 中醫治療室工作制度管理辦法
- 提花裝造工藝技術培訓課程
- 研究實驗報告水火箭.doc
評論
0/150
提交評論