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;