我很难理解为什么Dijkstra算法不适用于具有负边的无环有向图。据我所知，Dijkstra对图形进行了广度优先遍历，在适当的时候放松。例如，考虑图表：Dijkstra和负边缘
S->A (3)
S->B (4)
B->A (-2)
其中S是源节点。这是我想象它的工作：与4
2）递归对A的距离，马克B的距离
1）标志由于A分没有节点，什么也不做。
3）在B上行走。由于B指向A，检查B的距离+ B-> A是否小于A的当前距离。2 < 3，所以标记A的距离为2
然而，显然这不是它的工作原理，因为我使用这本书给出了这张图来说明底片为什么不起作用。我无法按照本书的解释。 Dijkstra如何在这张图表上工作，为什么他们不会使用我想象中的方法？
问题是，一旦你处理了一个节点，你不能在之后更新它的距离，因为那样会需要递归更新并且会抛弃整个东西（阅读：违背节点处理算法的假设单调增加到源的距离;查看算法的正确性证明以查看需要的地方）。所以一旦A被处理完毕，你不能再改变它的距离，这意味着你不能有负边缘，因为它们可能会让你距离以前处理过的节点更近。单调增加距离的假设是为什么在节点处理后将节点标记为黑色，之后忽略黑色节点。因此即使在图A中距离S到S的距离为2，Dijkstra的算法会给你一个3的距离，因为在A被处理之后，它忽略了通向A的任何边。
编辑：下面是Dijkstra算法会做：
1）标志为3的距离，把它放到等待处理节点的队列;标记B距离4，放入队列中。
2）因为它在前面，所以把A取出队列。由于A指向没有节点，所以不要更新任何距离，不要向队列添加任何内容。标记为已处理。
3）将B带出队列。 B指向A，但A被标记为已处理;忽略边B-→A。由于B不再有输出边缘，我们就完成了。
编辑2： 关于DAG，根本不需要Dijkstra算法。 DAG始终有一个拓扑排序，可以在O（| V | + | E |）中计算，并使用d(w) = min {d(w); d(v) + c(v, w)}作为更新距离的规则来处理拓扑顺序中的顶点，其中d(v)是顶点v与顶点之间的距离源和c(v,w)是边缘的长度(v,w)会给你正确的距离，再次在O（| V | + | E |）。总共有两个步骤，每个都需要O（| V | + | E |），所以这是计算具有任意边长度的DAG中的单源最短路径的总复杂度。