Relaxation step(Dijkstra's 最短路径算法)
2024-08-31 20:04:05
翻译成中文就是“松弛”,属于工程优化的范畴;
Dijkstra 的单源最短路径算法,有一个重要的步奏,当访问到新的结点 u (加入到集合 S),然后遍历 u 的邻接顶点(Adj),如果经由该点 u 到达 v 的最短距离,比之前的估计距离(tentative distance)还要小,则进行更新(update),更新步便叫做,relaxation step。
for v in Adj(u):
if d[v] > d[u] + weight(u, v):
d[v] = d[u] + weight(u, v)
u ~~~~~~~> v
\ ^
\ |
\----->s
1. 数学上对 relaxation 的解释
- Relaxation is making a change that reduces constraints. When the Dijkstra algorithm examines an edge, it removes an edge from the pool, thereby reducing the number of constraints.
One of the meanings of the English word “relaxation” is decreasing something. Because at 最短路径的更新阶段 you are essentially checking if you can decrease (optimize) the currently computed distance, I guess that’s why it is called “relaxation condition”.
What is the relaxation condition in graph theory
最新文章
- 图的生成树(森林)(克鲁斯卡尔Kruskal算法和普里姆Prim算法)、以及并查集的使用
- 高性能异步图片加载器的JS库:lazysizes
- DataGridView回车焦点横向移动
- SQL Server 全局变量
- Python创建list和按照索引访问list
- 使用ASP.Net WebAPI构建REST服务(三)——返回值
- SyntaxError: missing ; before statement 错误的解决
- ASP.NET MVC 路由进阶(之一)
- DES加密后get获取url参数无法解密问题
- Swift流程控制之循环语句和判断语句详解
- BZOJ 1607: [Usaco2008 Dec]Patting Heads 轻拍牛头
- 【Centos7】 firewalld命令行
- React——组件
- java代码的编译、执行过程
- iphone手机投屏在哪里 手机无线投屏电脑
- 【Vue】定义组件 data 必须是一个函数返回的对象
- 导出使用NPOI
- 【python接口自动化框架-unittest】如何传参数到下一个case
- Linux内核分析第六次作业
- Mingw下载