單源最短路徑的Dijkstra算法

1、 單源最短路徑的Dijkstra算法： 問題描述： 給定一個(gè)帶權(quán)有向圖G=（V，E），其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其他各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。算法描述： Dijkstra算法是解單源最短路徑的一個(gè)貪心算法?；舅枷胧牵涸O(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Di

2、jkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對數(shù)組dist做必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長度。源代碼：#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的最短特殊路徑長度/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;/初始都未用過該點(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ò)距離不在為無窮大u = j; / u保存當(dāng)前鄰接點(diǎn)中距離最小的點(diǎn)的號碼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 << "請輸入頂點(diǎn)個(gè)數(shù):" << endl;cin >> n;cout << "請輸入邊的個(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 << "請輸入每條邊的權(quán)_格式為： i j 權(quán)" << endl;for (k = 1; k <= m; k+)cin >> i;cin >> j;