多进程 android教程 Gradle caching cmd onclick icons rss vue开发教程 vue请求 pmp教学视频 jquery去空格 jquery多个元素绑定同一个事件 oracle无效的列索引 linux关闭mysql xcode打包 当前时间减一天 java使用redis mysql或者条件 svn安装后右键不显示 docker创建容器 python安装配置 input函数python python中import用法 python可视化编程 java类 数据结构java版 java环境配置 java的方法 java时间戳转日期 java原始数据类型 java多线程处理 python教程下载 sql综合利用工具 打马赛克的软件 linux解压tar 计算机网络自顶向下 3dmax插件神器 野德天赋 js分页
当前位置: 首页 > 学习教程  > 编程语言

prim算法和dijkstra算法的差别

2020/11/4 15:23:55 文章标签:

利用二维数组a[][]存放各点之间距离 Prim算法 dis[i] 中i 代表居民 dis[i].x代表与i居民相连接的x居民 用数组dis记录生成树到各个顶点的距离 用于求最小生成树(n个点相通的最小代价)(利用贪心),dis[]数组的更新策略…

利用二维数组a[][]存放各点之间距离

Prim算法

dis[i] 中i 代表居民 dis[i].x代表与i居民相连接的x居民
用数组dis记录生成树到各个顶点的距离
用于求最小生成树(n个点相通的最小代价)(利用贪心),dis[]数组的更新策略是dis[]数组中未访问过且j距离最小的点c(node),从此点开始计算如果dis[j]>a[node][j]则更新dis[j]为a[node][j] 即发现从未加入c的树->d 比c->d远(c为新加入树的点),则更新。

Dijkstra算法

用于求最短路径(即求起始点到任意点距离最短的情况),dis[]数组保存的是每个点到起始点的最近距离,dis[]更新策略选择dis[]数组中未访问过且最小的点c(node),从此点开始计算如果dis[j]>dis[node]+a[node][j]则更新dis[j]为dis[node]+a[node][j] 即发现从a->c->d 比a->d近,则更新。

本文链接: http://www.dtmao.cc/news_show_350374.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?