DAG只有负成本的最短路径
我正在寻找非循环有向图中source（s）和sink（t）之间的最短路径。 该图具有拓扑顺序（时间）。 所有的边都有或者为负或者为零。 还有可能使用Dijkstra算法吗？ 该图看起来像这样：图例
通常Dijkstra不能使用负权重，因为节点只探索一次（假设成本只能增加）。 在这种情况下，由于我只有负值（或零值成本），并且成本只能降低，所以如果我按照拓扑顺序浏览图，可以确保路径是最优的？
谢谢
是的，这将是最优的 - 但这不是Dijkstra的算法。
Dijkstra的算法根据目前的权重指定如何探索节点。 来自原文：
集合II的最短分支从该集合中移除并添加到集合I.结果一个节点从集合B转移到集合I.
你所描述的是一个不同的解决方案，它的工作原理是：
D[source] = 0
D[v] = min {D[u] + w(u,v) | u in V}
现在，由于您遵循拓扑秩序，因此您可以通过归纳证明上述公式是正确的 - 因为假设归纳假设对v之前探索的所有u都是正确的，所以D[v]也是正确的（因为它赢了将不会重新开放）。
PS这个证明甚至不需要假设只有负权重，如果权重是混合的，它就可以很好地工作，所以相同的解决方案就成立了。
因此，你所看到的是具有正权重的图表中最长的路径（你只需要取相反的值）。 这个问题实际上对于一般图而言是NP难的，但如果该图是有向无环图，则它可以在线性时间内解决。 例如，给出一个非常好的解释。
链接地址: http://www.djcxy.com/p/35187.html