《单源最短路径 贪心算法》由会员分享，可在线阅读，更多相关《单源最短路径 贪心算法(3页珍藏版)》请在人人文库网上搜索。
1、实验三 单源最短路径一、实验目的及要求掌握贪心算法的基本思想用c程序实现单源最短路径的算法二、实验环境Window下的vc三、实验内容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;ibegin;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;i1;i-)pathi=prevpathi+1;/构造路径m-;for (i=m;i;/输出路径coutn;int *dist=new int n+1;int *prev=new int n+1;int *c;c=new int *n+1;for (i=0;ibeginend;v=begin;Dijkstra(n,v,dist,prev,c);/计算路径PrintPath(prev,n,begin,end);/输出路径system(pause。
