版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 单源最短路径的Dijkstra算法: 问题描述: 给定一个带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。算法描述: Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是:设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Di
2、jkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist做必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其他顶点之间的最短路径长度。源代码:#include <iostream> #define MAX 1000#define LEN 100int k=0, bLEN;using namespace std;/-数据声明-/cij表示边 (i,j)的权/disti表示当前从源到顶点i的最短特殊路径长度/previ记录从源到顶点i的最短路径上的i的前一个顶点/-void Dijkstra(int n, int v, int d
3、ist, int prev, int cLEN)bool sLEN;/ 判断是否已存入该点到S集合中for (int i = 1; i <= n; i+)disti = cvi;si = false;/初始都未用过该点if (disti = MAX)previ = 0;/表示v到i前一顶点不存在elseprevi = v;distv = 0;sv = true;for (int i = 1; i < n; i+)int temp = MAX;int u = v;for (int j = 1; j <= n; j+)if (!sj) && (distj <
4、 temp) /j不在s中,v到j距离不在为无穷大u = j; / u保存当前邻接点中距离最小的点的号码temp = distj;su = true;k+;bk = u;cout << "-" << endl;cout << "迭代次数:" << i << endl;cout << "顶点为:"cout << v << "t"for (int i = 1; i <= k; i+)cout << bi &
5、lt;< "t"cout << endl;for (int j = 1; j <= n; j+)if (!sj) && cuj < MAX)int newdist = distu + cuj;if (newdist < distj)distj = newdist;/更新distprevj = u;/记录前驱顶点cout << "单源路径分别为:" << endl;for (int i = 2; i <= n; i+)if (disti != MAX)cout <<
6、; disti << " "cout << endl; cout << "-" << endl;/for (int i = 1; i <= n; i+)/ti = previ;int pLEN;for (int i = 2; i <= n; i+)cout << "dist" << i << "=" << disti << " "cout << "路径为:
7、" << v << "t"/*while (ti != v)cout << ti << "t"ti = prevti;*/int m = previ;int k=0;while (m != v)k+;pk = m;m = prevm;for (int x = k; x >= 1; x-)cout << px << "t"cout << i;cout << endl;int main()int i, j,k, m,n, v=1
8、;int distLEN, prevLEN, cLENLEN;cout << "请输入顶点个数:" << endl;cin >> n;cout << "请输入边的个数:" << endl;cin >> m;for (i = 1; i <= n; i+)for (j = 1; j <= n; j+)if (i = j)cij = 0;elsecij = MAX;cout << "请输入每条边的权_格式为: i j 权" << endl;for (k = 1; k <= m; k+)cin >> i;cin >> j;
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 柠檬酸充填封装工保密意识模拟考核试卷含答案
- 2026年黔西南民族职业技术学院高职单招笔试化学历年参考题库含答案解析
- 2026年黑龙江幼儿师范高等专科学校高职单招笔试化学历年参考题库含答案解析
- 2026年青海高等职业技术学院高职单招笔试数学历年参考题库含答案解析
- 2026年陕西交通职业技术学院高职单招笔试职业适应性测验历年参考题库含答案解析
- 2026年长春师范高等专科学校高职单招笔试语文历年参考题库含答案解析
- 电鸣乐器接装工工作质量竞赛考核试卷含答案
- 2026年重庆航天职业技术学院高职单招笔试综合素质历年参考题库含答案解析
- 2026年重庆房地产职业学院高职单招笔试语文历年参考题库含答案解析
- 2026年重庆大学城市科技学院高职单招笔试语文历年参考题库含答案解析
- 公路工程监理质量控制措施
- 身体约束管理制度流程
- 第8章TiAl系金属间化合物
- 沈阳城投新能源集团有限公司招聘笔试冲刺题2025
- 建筑表现生涯发展展示
- 与数同行 共话梦想-四年级数学期中家长会 课件
- 卫生院服务基层行资料-2.2.1.10 康复医疗服务★
- 《数据、模型与决策》 课件 3.2 DEA数据包络分析
- 劳动教育通论1-11章完整版课件
- GB/T 28856-2012硅压阻式压力敏感芯片
- 汉语教程第三册上第九课幸福的感觉
评论
0/150
提交评论