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

Question

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

Answer 1

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