单源最短路径的Dijkstra算法

单源最短路径的Dijkstra算法： 问题描述： 给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。算法描述： Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。源代码：#include #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 dist, 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 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 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 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 路径为： v t;/*while (ti != v)cout ti = 1; x-)cout px t;cout i;cout endl;int main()int i, j,k, m,n, v=1;int distLEN, prevLEN, cLENLEN;cout 请输入顶点个数: n;cout 请输入边的个数: 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