单源最短路径(贪心法)实验报告(共5页).docx

算法分析与设计实验报告第 5 次实验姓名学号班级时间12.12下午地点四合院 实验名称贪心法求最短路径实验目的通过上机实验，掌握贪心算法的思想，利用 Dijkstra 算法求解最短路径并实现。实验原理使用贪心法求出给定图各点的最短路径，并计算算法的执行时间，分析算法的有效性。已知一个有向网络 G=(V,E)和源点 V1，如上所示，求出从源点出发到图中其余顶点的最短路径。实验步骤1 用邻接矩阵表示有向图，并进行初始化，同时选择源点；2 选取候选集中距离最短的顶点，把其加入终点集合中；3 以该顶点为新考虑的中间顶点，修改候选集中各顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离；4 重复以上 2、3 步，直到所有候选集点都被加入到终点集中。关键代码void Dijkstra(int n,int v,int dist,int prev)bool smaxint;for(int i=1;i=n;i+)disti=