单源最短路径问题-dijkstra

《单源最短路径问题-dijkstra》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单源最短路径问题所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。Dijkstra算法基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。（1）初始时，S中仅含有源节点。（2）设u是G的某一个顶点，把从源到u且中间只

2、经过S中顶点的路称为从源到u的特殊路径，用数组D[i]记录顶点i当前所对应的最短特殊路径长度。（3）Dijkstra算法每次从V-S，中取出具有最短特殊路长度的顶点u将u添加到S中，同时对数组D作必要的修改。（4）一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。源程序1：//Dijkstra算法#include#includeusingnamespacestd;#defineVEX5//定义结点的个数#definemaxpoint100doublegraph[][maxpoint]={{0,10,-1,

3、30,100},{-1,0,50,-1,-1},{-1,-1,0,-1,10},{-1,-1,20,0,60},{-1,-1,-1,-1,0}};//邻接矩阵voidmain(){intR[maxpoint]={0},B[maxpoint];intD[VEX],P[VEX];//定义数组D用来存放结点特殊距离，P数组存放父亲结点//初始时，红点集中仅有源结点0R[0]=1;B[0]=0;for(inti=1;i

4、0;elseP[i]=-1;}//输出邻接矩阵for(i=0;i

5、//求蓝点集结点最小下标元素for(intj=min;jD[min]+graph[min][j]

6、

7、D[j]==-1){D[j]=D[min]+graph[min][j];//每次迭代求最小值

8、，最后一次即为到源点的最短路径P[j]=min;}//输出最短路径for(i=0;iusingnamespacestd;//////////////////////////////////////////////////////////////Graph.h#definemaxPoint100classCGraph{public:CGraph(void);~CGraph(

9、void);boolSetGraph(doubleg[maxPoint][maxPoint],intstartPoint,intsize);boolDijkstra();voidDisplay();intGetStartPoint();doubleGetBestWay(intdest,intpath[],int&pathLen);private:boolsolved;//标志当前图是否已经求解doublegraph[maxPoint][maxPoint];//当前图布局intsize;//地图大小intstartPoint;/