Dijkstra 算法 - DAG 最短路径只有负成本
Dijkstra’s algorithm - DAG Shortest path with ONLY negative costs
我正在寻找无环有向图中源（s）和汇（t）之间的最短路径。该图具有拓扑顺序（时间）。所有边都具有负成本或零成本。
是否仍然可以使用 Dijkstra 算法？
该图如下所示：graph example
通常 Dijkstra 不适用于负权重，因为节点只被探索一次（假设成本只会增加）。
在这种情况下，由于我只有负数（或零成本），并且成本只能减少，如果我按照拓扑顺序探索图形，是否确保路径是最优的？
谢谢
是的，这将是最优的 - 但这不是 Dijkstra 的算法。
Dijkstra 的算法指定了如何探索节点 - 根据它们的当前权重。来自 original article:
The shortest branch of set II is removed from this set and added to
set I. As a result one node is transferred from set B to set I .
您所描述的是一个不同的解决方案，并且有效：
D[source] = 0
D[v] = min {D[u] + w(u,v) | u in V}
现在，由于您遵循的是拓扑顺序，您可以通过归纳法证明上述公式是正确的 - 因为假设归纳假设对于 v 之前探索的所有 u 都是正确的，则D[v] 的结论也是正确的（因为它不会重新打开）。
P.S。这个证明甚至不需要只假设负权重，如果权重混合也能很好地工作，所以同样的解决方案成立。
因此，您正在查看的是图上具有正权重的最长路径（您只需取每个值的相反值）。这个问题对于一般图来说实际上是 NP-hard，但如果图是有向无环图，它就可以在线性时间内解决。例如给出了很好的解释here
我正在寻找无环有向图中源（s）和汇（t）之间的最短路径。该图具有拓扑顺序（时间）。所有边都具有负成本或零成本。 是否仍然可以使用 Dijkstra 算法？ 该图如下所示：graph example
通常 Dijkstra 不适用于负权重，因为节点只被探索一次（假设成本只会增加）。 在这种情况下，由于我只有负数（或零成本），并且成本只能减少，如果我按照拓扑顺序探索图形，是否确保路径是最优的？
谢谢
是的，这将是最优的 - 但这不是 Dijkstra 的算法。
Dijkstra 的算法指定了如何探索节点 - 根据它们的当前权重。来自 original article:
The shortest branch of set II is removed from this set and added to set I. As a result one node is transferred from set B to set I .
您所描述的是一个不同的解决方案，并且有效：
D[source] = 0
D[v] = min {D[u] + w(u,v) | u in V}
现在，由于您遵循的是拓扑顺序，您可以通过归纳法证明上述公式是正确的 - 因为假设归纳假设对于 v 之前探索的所有 u 都是正确的，则D[v] 的结论也是正确的（因为它不会重新打开）。
P.S。这个证明甚至不需要只假设负权重，如果权重混合也能很好地工作，所以同样的解决方案成立。
因此，您正在查看的是图上具有正权重的最长路径（您只需取每个值的相反值）。这个问题对于一般图来说实际上是 NP-hard，但如果图是有向无环图，它就可以在线性时间内解决。例如给出了很好的解释here