单源最短路径的Dijkstra算法

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;