社区讨论
关于约翰逊算法的重赋值过程?
学术版参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi6z1g3z
- 此快照首次捕获于
- 2025/11/20 13:09 4 个月前
- 此快照最后确认于
- 2025/11/20 13:09 4 个月前
前些日子在网上的博客里面学习了Johnson算法,也就是通过对边的重赋值使得对每个顶点进行Dijkstra算法的可行。
在已有的博客(和06年队爷的论文)资料中,都提到了重赋值的边权
CPPw'(u,v)=w(u,v)+h(u)-h(v);
但Johnson 全源最短路径算法
中的图书剪影最后一行指出,重赋值的边权是
CPPw'(u,v)=w(u,v)+h(v)-h(u);
本人在实现算法的时候,即按照上述h(v)-h(u)进行重赋值,并AC了codevs 1077 多源最短路。
所以上述的两种重赋值方法到底哪一种是正确的呢?
回复
共 5 条回复,欢迎继续交流。
正在加载回复...