单源最短路径 贪心算法(3页)Good is good, but better carries it.精益求精，善益求善。 实验三 单源最短路径一、实验目的及要求 掌握贪心算法的基本思想 用 c 程序实现单源最短路径的算法 二、实验环境 Window 下的 vc 2025三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最 短路径 3、Dijkstra 算法四、算法描述及实验步骤 设给定源点为 Vs，S 为已求得最短路径的终点集，开始时令 S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S 为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为 Vj ，则 Vj 只有：源点到终点有直接的弧 ；从 Vs 出发到 Vj 的这条最短路径所经过的所有中间顶点必定在 S中。即只有这条最短路径的最后一条弧才是从 S 内某个顶点连接到 S 外的顶点Vj 。 若定义一个数组 dist[n]，其每个 dist[i]重量保存从 Vs 出发中间只经过集合 S中的顶点而到达 Vi 的所有路径中长度最小的路径长度值，则下一条最短路径的终点 Vj 必定是不在 S 中且值最小的顶点， 即：dist[i]=Min{ dist[k]| Vk∈V-S } 利用公式就可以依次找出下一条最短路径。 在程序中 c[][]表示带权邻接矩阵 ， dist[]表示顶点到源点的最短路径 ， p[]记录顶点到源点最短路径的前驱节点 ， u 源点，函数 Way 是递归的构造出最短路径的次序。 五、实验结果 程序执行的结果：六、源代码#include #includeusing namespace std;#define MAX 999void getdata(int **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)c[i][j]=0;elsec[i][j]=MAX;}}do {cout<<"请输入 起点 终点 权值(-1 退出)：";cin>>begin;if(begin==-1) break;cin>>end>>weight;c[begin][end]=weight;} while(begin!=-1);}void Dijkstra(int n,int v ,int *dist,int *prev,int **c){bool s[MAX];int i,j;for (i=1;i<=n;i++){dist[i]=c[v][i];//从源点到各点的值s[i]=false;if(dist[i]==MAX) prev[i]=0;//最大值没有路径else prev[i]=v;//前驱为源点}dist[v]=0;s[v]=true;for (i=1;i<=n;i++) {int temp=MAX;int u=v;for(j=1;j<=n;j++)if((!s[j])&&(dist[j]
