查找图中没有任何负前缀的最短路径

本文介绍了查找图中没有任何负前缀的最短路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在有正负边的有向图中找到从源到目的地的最短路径，以使路径中的任何点之前的边之和为负.如果没有这样的路径，也要报告.

Find the shortest path from source to destination in a directed graph with positive and negative edges, such that at no point in the path the sum of edges coming before it is negative. If no such path exists report that too.

我试图使用改良的Bellman Ford，但找不到正确的解决方案.

I tried to use modified Bellman Ford, but could not find the correct solution.

我想澄清几点:

是，体重循环可能为负数.

n是边的数量.

如果问题有解决方案，则假定存在O(n)个长度路径.

+ 1/-1边缘权重.

yes there can be negative weight cycles.

n is the number of edges.

Assume that a O(n) length path exists if the problem has a solution.

+1/-1 edge weights.

推荐答案

诚然，这不是一个建设性的答案，但是在评论中发布太久了……

Admittedly this isn't a constructive answer, however it's too long to post in a comment...

在我看来，这个问题包含二进制和离散背包问题，因此，最坏情况下的运行时间充其量是伪多项式.考虑一个按如下所示连接和加权的图:

It seems to me that this problem contains the binary as well as discrete knapsack problems, so its worst-case-running-time is at best pseudo-polynomial. Consider a graph that is connected and weighted as follows:

然后，等效的二进制背包问题正在尝试从集合{ a 0 ，...， a 中选择权重 n }最大化Σ a i ，其中Σ a i < X .

Then the equivalent binary knapsack problem is trying to choose weights from the set {a0, ..., an} that maximizes Σ ai where Σ ai < X.

作为附带说明，如果我们引入加权循环，则可以轻松构造无界背包问题.

As a side note, if we introduce weighted loops it's easy to construct the unbounded knapsack problem instead.

因此，您可能选择的任何实用算法的运行时间取决于您认为平均"情况的时间.对我未曾考虑或无法解决的问题是否有限制?您似乎很确定这是一个O( n 3 )问题.(尽管在这种情况下 n 是什么?)

Therefore, any practical algorithm you might choose has a running time that depends on what you consider the "average" case. Is there a restriction to the problem that I've either not considered or not had at my disposal? You seem rather sure it's an O(n3) problem. (Although what's n in this case?)