最短路径算法边的权值的思考
关于最短路径算法中边的权值的思考
不管是单源最短路径算法:Dijkstra Bellman-ford
还是多源最短路径算法:floyed Johnson
我们都绕不开的一件事就是,边的权值 w i , j w_{i,j} wi,j
下面我们从多个角度谈边的权值
1.权值恒定
它是指对于每条边的权值 w i , j w_{i,j} wi,j,只要i,j确定, w i , j w_{i,j} wi,j就保持不变。这时,这张图应该是一个静态的图。
1.1 如果权值全部非负
这时我们可以将 w i , j w_{i,j} wi,j理解为从节点i到节点j的距离,我们可以使用Dijkstra算法求出单源最短路径,但是此时我们无法使用Dijkstra求出单源最长路径,因为Dijkstra算法是一种贪心算法,他每次都找到最优的点,即距离最远的点,而最长路径中,不一定每一个点都是局部最优的。
所以我们说,Dijkstra算法只适用于全局最优要求局部最优的情况。
不过如果我们使用Bellman-ford算法,我们就可以求出最长路径,而且能够判断是否存在正环。即我们的改动就是,“松弛操作”:
初始情况下,s.d=0,其他所有节点距离s点的距离为负无穷
//松弛边 Edge(u,v)
relax(u,v)
if( v.d<u.d w(u,d)
v.d=u.d w(u,d)
1.2 如果权值有正有负
这时我们不能采用Dijkstra算法求最长路径或者最短路径
但是,我们仍然可以使用Bellman-ford算法求出最短路径和最长路径,还能判断是否存在正环或者负环,这一切都取决于我们的松弛操作的设计
2.权值非恒定
这是指 w i , j w_{i,j} wi,j,在i和j确定情况下,它还会随其他因素变化,最经典的情况就是, w i , j = f ( i . d , j . d ) w_{i,j}=f(i.d,j.d) wi,j=f(i.d,j.d)
即它和i j两点到源节点s的距离有关,而我们知道i.d
和j.d
会随着程序运行而发生改变,即程序运行过程中,边的权值会发生改变。
此时我们仍然可以使用Bellman-ford算法来计算最短路径或者是最长路径。
这是因为,虽然随着程序的运行,每个节点v到源点s的距离会变化,但是我们要知道的是:Bellman-ford算法的终止情形是:不存在可松弛边。
一种情况是:边权值的变化导致了v.d
的变化,而v.d
的变化又会导致了边权值的变化从而周而复始,无法结束,这时我们就称 这个图中存在负环或者正环,导致无法求出最短路径或者最长路径。
另一种情况是:你优化你的路径方案后,你去修改图的状态,如果此时你发现基于目前的图的状态,你无法继续优化你的路径方案,那就不会修改图的状态,那就意味者程序结束。这时我们的算法就成功找到了路径方案
所以,只要当方案不发生变化,即i.d
和j.d
不发生变化 , w i , j w_{i,j} wi,j就不在改变时,即使w_{i,j}
会随着程序运行发送变化,我们仍然可以使用bellman-ford算法计算最长或最短路径
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgehgke
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01