单源最短路径 贪心算法(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
