学网站建设怎么样,代码运行框wordpress,工程管理毕业设计代做网站,大学网站开发与管理课程心得体会关于最短路径算法中边的权值的思考
不管是单源最短路径算法#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算法计算最长或最短路径
