spfa

首先dij,如何看待不能处理带负边的情况,因为dij的算法是目前到达的一定是最优的,如果有负边存在将会改变这种情况,可能之前到达时某点是最差情况但后面加个负数就变成最优了
其次 spfa 因为它的算法过程是不断更新某点的最短路径估值(松弛操作) 所以即使后面存在负边,也会更新前面的操作,从而得到最优结果;


全部评论

相关推荐

浩浩没烦恼:一二面加起来才一个小时? 我一面就一个小时多了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务