单源最短路径（贪心算法）报告.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.07M 资料格式：doc 举报版权申诉

第1页 / 共6页

qq_42236488-12054796-单源最短路径（贪心算法）报告.doc.pdf-第2页.png

第2页 / 共6页

qq_42236488-12054796-单源最短路径（贪心算法）报告.doc.pdf-第3页.png

第3页 / 共6页

qq_42236488-12054796-单源最短路径（贪心算法）报告.doc.pdf-第4页.png

第4页 / 共6页

qq_42236488-12054796-单源最短路径（贪心算法）报告.doc.pdf-第5页.png

第5页 / 共6页

qq_42236488-12054796-单源最短路径（贪心算法）报告.doc.pdf-第6页.png

第6页 / 共6页

实验十一：单源最短路径（贪心算法）报告

1．问题描述

2．实验目的

3．实验原理

4．实验设计

5．实验结果与分析

6．结论

7．程序源码

实验十一：单源最短路径（贪心算法）报告 2017061111 李静娴 1．问题描述给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V 中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 2．实验目的（1）熟悉贪心算法，并学以致用（2）熟练掌握单源最短路径算法 3．实验原理 Dijkstra 算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时，S 中仅含有源。设 u 是 G 的某一个顶点，把从源到 u 且中间只经过 S 中顶点的路称为从源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S 中取出具有最短特殊路长度的顶点 u，将 u 添加到 S 中，同时对数组 dist 作必要的修改。一旦 S 包含了所有 V 中顶点， dist 就记录了从源到所有其他顶点之间的最短路径长度。 Dijkstra 算法可描述如下，其中输入带权有向图是 G=(V,E)，V={1,2,…，n}，顶点 v 是源。 c 是一个二维数组，c[i][j]表示边(i,j)的权。当(i,j)不属于 E 时，c[i][j]是一个大数。dist[i]表示当前从源到顶点 i 的最短特殊路径长度。在 Dijkstra 算法中做贪心选择时，实际上是考虑当 S 添加 u 之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的 S 到达顶点 u,然后从 u 经过一条边直接到达顶点 i，则这种路的最短长度是 dist[u]+c[u][i]。如果 dist[u]+c[u][i]上的权值。设 S 为已知最短路径的终点的集合,它的初始状态为空集。从源点 v 经过 S 到图上其余各点 vi 的当前最短路径长度的初值为：dist[i]=c[v][i], vi 属于 V. (2) 选择 vu, 使得 dist[u]=Min{dist[i] | vi 属于 V-S},vj 就是长度最短的最短路径的终点。令 S=S U {u}. (3) 修改从 v 到集合 V-S 上任一顶点 vi 的当前最短路径长度:如果 dist[u]+c[u][j]< dist[j] 则修改 dist[j]= dist[u]+c[u][j]. (4) 重复操作(2),(3)共 n-1 次。算法的时间复杂度：O((E+V)lgV ) 空间复杂度：O(E) 对于一个图 G(V,E)来说，V 是顶点，E 是边。 4．实验设计

（1）输入数据格式：节点个数 N 由宏定义给出，有向图权值矩阵由用户设定生成方式：用户输入权值矩阵数据规模：宏定义设定。（2）该程序先是设定好节点个数。然后用户输入权值矩阵。再调用 Dijkstra(N, v, dist, prev, c) 函数，dist[i]表示当前从源到顶点 i 的最短特殊路径长度，即最优解，prev[i]记录从源到顶点 i 的最短路径 i 的前一个顶点，最后调用 Traceback(1, i, prev)函数输出从源点到各个节点的最短路径，即最优值。（3）程序运行的结果有两部分，先是打印有向图权值矩阵，再分别输出源点到各个节点的最短路径长度和最短路径。 5．实验结果与分析

在有向图权的矩阵 c[i][j]中，c[i][j]表示节点 vi 到节点 vj 的直线距离。根据打印出来的矩阵，可以画出带权有向图，然后就可以检验程序得出的结果。经人工分析，所得结果与程序运算一致，可见程序计算结果无误。 6．结论我采用有向图权的矩阵的方式刻画有向带权图的结构，这样就可以根据程序结果画出有向带权图，从而验证程序运行结果的正确性。本程序可以通过修改宏定义节点个数 N 的值，生成不同规模的有向带权图。 7．程序源码 #include #include using namespace std; const int N = 5; const int M = 1000; template void Dijkstra(int n, int v, Type dist[], int prev[], Type c[][N + 1]); void Traceback(int v, int i, int prev[]);//输出最短路径 v 源点，i 终点 int main() { int v = 1;//源点为 1 int dist[N + 1], prev[N + 1], c[N + 1][N + 1]; cout << "有向图权的矩阵为：" << endl; for (int i = 1; i <= N; i++)

{ } for (int j = 1; j <= N; j++) { cin >> c[i][j]; } cout << endl; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { cout << c[i][j] << " "; } cout << endl; } Dijkstra(N, v, dist, prev, c); for (int i = 2; i <= N; i++) { cout << "源点 1 到点" << i << "的最短路径长度为:" << dist[i] << "，其路径为"; Traceback(1, i, prev); cout << endl; } return 0; } template void Dijkstra(int n, int v, Type dist[], int prev[], Type c[][N + 1]) { bool s[N + 1]; for (int i = 1; i <= n; i++) { dist[i] = c[v][i];//dist[i]表示当前从源到顶点 i 的最短特殊路径长度 s[i] = false; if (dist[i] == M) { prev[i] = 0;//记录从源到顶点 i 的最短路径 i 的前一个顶点 } else {

prev[i] = v; } } dist[v] = 0; s[v] = true; for (int i = 1; i < n; i++) { int temp = M; int u = v;//上一顶点 //取出 V-S 中具有最短特殊路径长度的顶点 u for (int j = 1; j <= n; j++) { if ((!s[j]) && (dist[j] < temp)) { u = j; temp = dist[j]; } } s[u] = true; //根据作出的贪心选择更新 Dist 值 for (int j = 1; j <= n; j++) { if ((!s[j]) && (c[u][j] < M)) { Type newdist = dist[u] + c[u][j]; if (newdist < dist[j]) { dist[j] = newdist; prev[j] = u; } } } } } //输出最短路径 v 源点，i 终点 void Traceback(int v, int i, int prev[]) { if (v == i) {

cout << i; return; } Traceback(v, prev[i], prev); cout << "->" << i; }

分享到：

赞收藏

资料库

单源最短路径（贪心算法）报告.doc

相关推荐

课程资源

热门标签

最新资料