




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 單源最短路徑的Dijkstra算法: 問(wèn)題描述: 給定一個(gè)帶權(quán)有向圖G=(V,E),其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外,還給定V中的一個(gè)頂點(diǎn),稱(chēng)為源。現(xiàn)在要計(jì)算從源到所有其他各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱(chēng)為單源最短路徑問(wèn)題。算法描述: Dijkstra算法是解單源最短路徑的一個(gè)貪心算法。基本思想是:設(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí),S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn),把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱(chēng)為從源到u的特殊路徑,并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Di
2、jkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u,將u添加到S中,同時(shí)對(duì)數(shù)組dist做必要的修改。一旦S包含了所有V中頂點(diǎn),dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度。源代碼:#include <iostream> #define MAX 1000#define LEN 100int k=0, bLEN;using namespace std;/-數(shù)據(jù)聲明-/cij表示邊 (i,j)的權(quán)/disti表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長(zhǎng)度/previ記錄從源到頂點(diǎn)i的最短路徑上的i的前一個(gè)頂點(diǎn)/-void Dijkstra(int n, int v, int d
3、ist, int prev, int cLEN)bool sLEN;/ 判斷是否已存入該點(diǎn)到S集合中for (int i = 1; i <= n; i+)disti = cvi;si = false;/初始都未用過(guò)該點(diǎn)if (disti = MAX)previ = 0;/表示v到i前一頂點(diǎn)不存在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(luò)距離不在為無(wú)窮大u = j; / u保存當(dāng)前鄰接點(diǎn)中距離最小的點(diǎn)的號(hào)碼temp = distj;su = true;k+;bk = u;cout << "-" << endl;cout << "迭代次數(shù):" << i << endl;cout << "頂點(diǎn)為:"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;/記錄前驅(qū)頂點(diǎn)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 << "請(qǐng)輸入頂點(diǎn)個(gè)數(shù):" << endl;cin >> n;cout << "請(qǐng)輸入邊的個(gè)數(shù):" << endl;cin >> m;for (i = 1; i <= n; i+)for (j = 1; j <= n; j+)if (i = j)cij = 0;elsecij = MAX;cout << "請(qǐng)輸入每條邊的權(quán)_格式為: i j 權(quán)" << endl;for (k = 1; k <= m; k+)cin >> i;cin >> j;
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年中國(guó)三足式袋卸料離心機(jī)數(shù)據(jù)監(jiān)測(cè)研究報(bào)告
- 深度解析教育科技行業(yè)未來(lái)發(fā)展方向
- 教育機(jī)構(gòu)如何利用游戲化平臺(tái)提高教學(xué)效果
- 企業(yè)培訓(xùn)中多媒體技術(shù)的應(yīng)用與創(chuàng)新-以智慧教室為例
- 新版培訓(xùn)課件模板圖片
- 碧桂園張家港拓客內(nèi)部培訓(xùn)89
- 全民健身設(shè)施補(bǔ)短板工程實(shí)施方案在城市老舊小區(qū)健身設(shè)施改造中的應(yīng)用研究
- 全球鈾礦資源市場(chǎng)前景與2025年核能產(chǎn)業(yè)綠色低碳發(fā)展戰(zhàn)略報(bào)告
- 公交優(yōu)先戰(zhàn)略在2025年城市交通擁堵治理中的可持續(xù)發(fā)展報(bào)告
- Carpetimycin-B-生命科學(xué)試劑-MCE
- 板式換熱器、半容積式換熱器換熱器面積計(jì)算表(自動(dòng)計(jì)算)
- 直流屏檢修作業(yè)指導(dǎo)書(shū)
- 冷鐓機(jī) 質(zhì)量要求技術(shù)條件
- 《全國(guó)統(tǒng)一安裝工程預(yù)算定額》工程量計(jì)算規(guī)則
- translated-NCCN臨床實(shí)踐指南:非小細(xì)胞肺癌(中文版2022.V5)
- GB/T 8312-2002茶咖啡堿測(cè)定
- 通信線(xiàn)路工程施工組織設(shè)計(jì)方案【實(shí)用文檔】doc
- 護(hù)士注冊(cè)健康體檢表下載【可直接打印版本】
- 預(yù)計(jì)財(cái)務(wù)報(bào)表編制及分析課件
- Q∕SY 1347-2010 石油化工蒸汽透平式壓縮機(jī)組節(jié)能監(jiān)測(cè)方法
- 西門(mén)子順序功能圖語(yǔ)言S7-Graph的應(yīng)用
評(píng)論
0/150
提交評(píng)論