社区讨论

关于约翰逊算法的重赋值过程?

学术版参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi6z1g3z
此快照首次捕获于
2025/11/20 13:09
4 个月前
此快照最后确认于
2025/11/20 13:09
4 个月前
查看原帖
前些日子在网上的博客里面学习了Johnson算法,也就是通过对边的重赋值使得对每个顶点进行Dijkstra算法的可行。
在已有的博客(和06年队爷的论文)资料中,都提到了重赋值的边权
CPP
w'(u,v)=w(u,v)+h(u)-h(v);
Johnson 全源最短路径算法 中的图书剪影最后一行指出,重赋值的边权是
CPP
w'(u,v)=w(u,v)+h(v)-h(u);
本人在实现算法的时候,即按照上述h(v)-h(u)进行重赋值,并AC了codevs 1077 多源最短路。
所以上述的两种重赋值方法到底哪一种是正确的呢?

回复

5 条回复,欢迎继续交流。

正在加载回复...