YZBPXX
YZBPXX
图论—最短单源路径
spfa
全部文章
图论&mdas...
acm入门练习(1)
c#(1)
c++,c实用小函数,操作(20)
hash/bkdr hash字符串(2)
动态规划—树形dp(1)
动态规划—背包九讲(7)
单调栈(1)
图论—bfs(2)
图论—dfs(6)
图论—最小生成树(1)
字符串—ac自动机(1)
字符串—扩展KMP/KMP(4)
字符串—马拉车(1)
带权并查集(2)
拓扑排序(2)
数据库学习(6)
数据结构—RMQ(5)
数据结构—字典树(1)
数据结构--红黑二叉树(1)
数论(8)
未归档(2)
矩阵快速幂(1)
算法分析(3)
网络流(1)
集训题(2)
题解(33)
归档
标签
去牛客网
登录
/
注册
spfa
542 浏览
0 回复
2019-08-05
YZBPXX
+关注
首先dij,如何看待不能处理带负边的情况,因为dij的算法是目前到达的一定是最优的,如果有负边存在将会改变这种情况,可能之前到达时某点是最差情况但后面加个负数就变成最优了
其次 spfa 因为它的算法过程是不断更新某点的最短路径估值(松弛操作) 所以即使后面存在负边,也会更新前面的操作,从而得到最优结果;
模版
举报
收藏
赞
评论加载中...