单源最短路径 贪心算法

1、实验三 单源最短路径一、实验目的及要求掌握贪心算法的基本思想用c程序实现单源最短路径的算法二、实验环境Window下的vc2010三、实验内容1、有向图与单源点最短路径2、按路径长度非降的次序依次求各节点到源点的最短路径3、Dijkstra算法四、算法描述及实验步骤设给定源点为Vs，S为已求得最短路径的终点集，开始时令S=Vs。当求得第一条最短路径(Vs，Vi)后，S为Vs，Vi。根据以下结论可求下一条最短路径。设下一条最短路径终点为Vj，则Vj只有：源点到终点有直接的弧；从Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的

2、顶点Vj。若定义一个数组distn，其每个disti分量保存从Vs出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：disti=Mindistk|VkV-S利用公式就可以依次找出下一条最短路径。在程序中c表示带权邻接矩阵，dist表示顶点到源点的最短路径，p记录顶点到源点最短路径的前驱节点，u源点，函数Way是递归的构造出最短路径的次序。五、实验结果程序执行的结果：六、源代码#include #includeusing namespace std;#define MAX 999void getdata(int *

3、c,int n)int i,j;int begin,end,weight;for (i=1;i=n;i+)for (j=1;j=n;j+)if(i=j)cij=0;elsecij=MAX;do coutbegin;if(begin=-1) break;cinendweight;cbeginend=weight; while(begin!=-1);void Dijkstra(int n,int v ,int *dist,int *prev,int *c)bool sMAX;int i,j;for (i=1;i=n;i+)disti=cvi;/从源点到各点的值si=false;if(disti=M

4、AX) previ=0;/最大值没有路径else previ=v;/前驱为源点distv=0;sv=true;for (i=1;i=n;i+) int temp=MAX;int u=v;for(j=1;j=n;j+)if(!sj)&(distjtemp) u=j;temp=distj;/不在集合里，值temp，选最小值su=true;for (j=1;j=n;j+) if(!sj)&(cujMAX)int newdist=distu+cuj;if(newdist1;i-)pathi=prevpathi+1;/构造路径m-;for (i=m;i=end;i+) coutpathi;/输出路径coutbb endl;void main()int n,i;int v=1;coutn;int *dist=new int n+1;int *prev=new int n+1;int *c;c=new int *n+1;for (i=0;i=n;i+)ci=new int n+1;getdata(c,n);/获取数据int begin=1,end;coutbeginend;v=begin;Dijks