单源最短路径的Dijkstra算法

《单源最短路径的Dijkstra算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单源最短路径的Dijkstra算法：问题描述：给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。算法描述：Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊

2、路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。源代码：#include#defineMAX1000#defineLEN100intk=0,b[LEN];usingnamespacestd;//-------------------------------------数据声明---------

3、---------------------------------------//c[i][j]表示边(i,j)的权//dist[i]表示当前从源到顶点i的最短特殊路径长度//prev[i]记录从源到顶点i的最短路径上的i的前一个顶点//---------------------------------------------------------------------------------------------voidDijkstra(intn,intv,intdist[],intprev[],intc[][

4、LEN]){bools[LEN];//判断是否已存入该点到S集合中for(inti=1;i<=n;i++){dist[i]=c[v][i];s[i]=false;//初始都未用过该点if(dist[i]==MAX)prev[i]=0;//表示v到i前一顶点不存在elseprev[i]=v;}dist[v]=0;s[v]=true;for(inti=1;i

5、j距离不在为无穷大{u=j;//u保存当前邻接点中距离最小的点的号码temp=dist[j];}s[u]=true;k++;b[k]=u;cout<<"----------------------------------------------------------"<

6、((!s[j])&&c[u][j]

7、------"<=1

8、;x--)cout<>n;cout<<"请输入边的个数:"<>m;f