【为什么Dijkstra算法不适用边长为负数的情况】 原文地址：http://lixing123.com/?p=280
Dijkstra算法(这个荷兰词真难读。。。不过Dijkstra是一位非常NB的计算机科学家，goto有害论、信号量和PV原语、哲学家聚餐问题、银行家算法等等，都是这位大牛搞出来的)，是有向/无向加权图(就是每条边都有长度)中，计算两个点之间最短距离的有效方法，在使用堆排序的情况下，它的时间复杂度为O(Nlog(N+M))，(这里N代表节点数，M代表边数)很接近线性了，还是非常好的。
不过，Dijkstra算法有一个限制，就是它只适用于边长不为负的图。如果一张图里有负数长的边长，那么Dijkstra算法就不适用了。这时候就需要另外的算法了。
为什么不适用呢？其实很容易就可以找到反例。假设一张加权图，有的边长为负数。假设边长最小为-10，我们把所有的边长都加上10，就这就可以得到一张无负值加权图。此时用Dijkstra算法算出一个从节点s到节点t的最短路径L，L共包括n条边，总长为t；那么对于原图，每条边都要减去10，所以原图中L的长度是t-10*n。这是Diskstra算法算出的结果。
那么问题来了：对于加上10之后的图，假设还有一个从s到t的路径M，长度为t1，它共包括n1条边，比L包含的边长多，那么还原回来之后，每条边需要减去10，那么M的总长就是t1-10*n1。那么，是不是M的总长一定比L的总长更长一些呢？不一定。假如n1>n，也就是说M的边数比L的边数更多，那么M减去的要比L减去的更多，那么t1-10*n1
另外，如果一张图里有负数边，但没有总长为负数的环，此时可以用Bellman-Ford算法计算。虽然它比Dijkstra慢了一些，但人家应用范围更广啊。
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络