dijkstra 算法算法(这个荷兰词真难读。不过dijkstra 算法是一位非常NB的计算机科学家，goto有害论、信号量和PV原语、哲学家聚餐问题、银行家算法等等都是这位大牛搞出来的)，是有向/无姠加权图(就是每条边都有长度)中计算两个点之间最短距离的有效方法，在使用堆排序的情况下它的时间复杂度为O(Nlog(N+M))，(这里N代表节点数M玳表边数)很接近线性了，还是非常好的
不过，dijkstra 算法算法有一个限制就是它只适用于边长不为负的图。如果一张图里有负数长的边长那么dijkstra 算法算法就不适用了。这时候就需要另外的算法了
为什么不适用呢？其实很容易就可以找到反例假设一张加权图，有的边长为负數假设边长最小为-10，我们把所有的边长都加上10就这就可以得到一张无负值加权图。此时用dijkstra 算法算法算出一个从节点s到节点t的最短路径LL共包括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<t-10*n是可能的此时dijkstra 算法算法是不成立的。
另外还有一种更简单的例子：假如一张图里有一个总长为负数的环，那么dijkstra 算法算法有可能会沿着这个环一直繞下去绕到地老天荒。。
另外如果一张图里有负数边，但没有总长为负数的环此时可以用计算。虽然它比dijkstra 算法慢了一些但人家應用范围更广啊。
