网站建设售后培训,北京设计网站的公司哪家好,自助建站免费建站五个平台,做网推的网站关于最短路径算法中边的权值的思考
不管是单源最短路径算法#xff1a;Dijkstra Bellman-ford 还是多源最短路径算法#xff1a;floyed Johnson 我们都绕不开的一件事就是#xff0c;边的权值wi,jw_{i,j}wi,j 下面我们从多个角度谈边的权值
1.权值恒定
它是指对于每条边…关于最短路径算法中边的权值的思考
不管是单源最短路径算法Dijkstra Bellman-ford 还是多源最短路径算法floyed Johnson 我们都绕不开的一件事就是边的权值wi,jw_{i,j}wi,j 下面我们从多个角度谈边的权值
1.权值恒定
它是指对于每条边的权值wi,jw_{i,j}wi,j,只要i,j确定,wi,jw_{i,j}wi,j就保持不变。这时,这张图应该是一个静态的图。
1.1 如果权值全部非负
这时我们可以将wi,jw_{i,j}wi,j理解为从节点i到节点j的距离,我们可以使用Dijkstra算法求出单源最短路径,但是此时我们无法使用Dijkstra求出单源最长路径,因为Dijkstra算法是一种贪心算法,他每次都找到最优的点,即距离最远的点,而最长路径中,不一定每一个点都是局部最优的。
所以我们说,Dijkstra算法只适用于全局最优要求局部最优的情况。
不过如果我们使用Bellman-ford算法,我们就可以求出最长路径,而且能够判断是否存在正环。即我们的改动就是,“松弛操作”:
初始情况下,s.d0,其他所有节点距离s点的距离为负无穷
//松弛边 Edge(u,v)
relax(u,v)if( v.du.dw(u,d)v.du.dw(u,d)1.2 如果权值有正有负
这时我们不能采用Dijkstra算法求最长路径或者最短路径
但是,我们仍然可以使用Bellman-ford算法求出最短路径和最长路径,还能判断是否存在正环或者负环,这一切都取决于我们的松弛操作的设计
2.权值非恒定
这是指wi,jw_{i,j}wi,j,在i和j确定情况下,它还会随其他因素变化,最经典的情况就是,wi,jf(i.d,j.d)w_{i,j}f(i.d,j.d)wi,jf(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不发生变化 ,wi,jw_{i,j}wi,j就不在改变时,即使w_{i,j}会随着程序运行发送变化,我们仍然可以使用bellman-ford算法计算最长或最短路径
