有向无环图中的最短正路径

Question

给定一个边上任意权重的有向无环图和两个特定节点s和t，其中s的入度和t的出度为0。如何确定从s到的最短路径有正成本吗？

Answer 1

使用修改后的 Bellman-Ford，如果生成的最短路径成本 <0，则从图中删除边，直到达到成本，即 <0。