我有一个有循环的有向图。所有边都被加权，并且权重可以是负数。可能存在负循环。
我想找到一条从 s 到 t 的路径，它可以最小化路径上的总权重。当然，当存在负循环时，它可以变为负无穷大。但是如果我不允许路径中的循环（不在原始图中）怎么办？即一旦路径离开一个节点，就不能再次进入该节点。
这肯定避免了负无穷大问题，但令人惊讶的是，在 Google 上搜索没有找到已知算法。最接近的是 Floyd-Warshall 算法，但它不允许负循环。
提前非常感谢。
编辑：我可能过于概括了我原来的问题。实际上，我得到了一个具有非负边权重的循环有向图。但除此之外，每个节点也有一个积极的奖励。我想找到一个简单的路径，它最小化（路径上的边权重总和）-（路径覆盖的节点奖励总和）。这肯定可以转换为我发布的问题，但是丢失了一些结构。来自子模块分析的一些提示表明，这个激励问题不是 NP 难的。非常感谢