如果出现下图所示的负循环，会有相关点的当前最短路径为undefined（即无法定义）。

之前我们也看过通用的最短路径算法思路，如下图所示：

这种通用算法会有两个问题：

1. 时间复杂度呈指数性。
2. 如果出现负循环，最短路径的计算会无法中止。

第一个问题能被Dijkstra算法解决，但它不能解决负循环带来的问题，而这节课讲的Bellman-Ford算法适用于负权重和负循环的图下进行最短路径的计算。

Bellman-Ford算法一个大概的计算思路如下：

简单来说，就是对所有点正常relax edge完后，进行一个检查操作，如果还存在d[v] > d[u] + w(u,v)的情况，说明该图存在负循环。

它的证明过程如下图所示，总结来说就是负循环的出现会导致起始点到终点的最短路径上的节点大于|V|-1，因为负循环会不断让最短路径陷入一个死循环当中。

最新文章

1. IntelliJ IDEA常用快捷键windows
2. 问题解决_WCF_WCF 接收我服务的 HTTP 响应时发生错误
3. 连接mysql提示com.mchange.v2.resourcepool.BasicResourcePool
4. 电脑控制台灯(c# hook,显示室温,联网校正时间)
5. android保存图片的方式
6. My First Django Project - <Django + MySQL + Ajax> (1)
7. 用QT创建WINDOWS服务程序
8. cin的返回值
9. lambda和委托
10. 深度揭秘腾讯云TSF日调用量超万亿次背后技术架构
11. JavaScript进阶-this
12. 在Ubuntu上升级SQLite，并让Python使用新版SQLite
13. Aizu - 2249 Road Construction
14. nginx重新编译添加ssl模块
15. Activity服务类-4 HistoryService服务类
16. C++ 文本查询2.0(逻辑查询)
17. Android 录制视频
18. 编写nios-shell时想到的问题-回车vs换行
19. 系统管理模块_岗位管理_改进_使用ModelDroven方案_套用美工写好的页面效果_添加功能与修改功能使用同一个页面
20. Spring和quartz整合的入门使用教程

热门文章

1. CRF基础知识以及如何实现Learning，Inference
2. 多测师讲解接口测试 _fiddler无法打开浏览器_高级讲师肖sir
3. go-zero 如何应对海量定时/延迟任务？
4. day52 Pyhton 前端03
5. Go net/http包
6. abp(net core)+easyui+efcore实现仓储管理系统——出库管理之三(五十一)
7. Spark核心组件通识概览
8. go 爬取页面保存
9. Ubuntu服务安装
10. ASP.NET 获取客户端IP地址