图中两个节点之间的最短路径的索赔？
如果加权和有向图G上的两个顶点之间的最短路径（可能具有负边）由D(u, v) ，则下面的权利要求总是假的。
具有负边，但没有任何负循环，则D（u，v）上的Sigma（所有顶点对上的和）不能为负。
Why this claims is False?
什么是D(u,v)哪里没有从u到v的路径没有在笔记中给出，但我认为在这种情况下D(u,v)=0 。
假设如果没有从u到v路径，那么D(u,v) = infinity （我确实没有理由另外假设D(u,v)=0在这种情况下假设D(u,v)=0是奇怪的），则声明是真实的。
证明：
首先，假设每对u,v都有一条路径 - 否则所有对的和都是无穷大，我们就完成了。
对于每对顶点u,v ：
D(u,v)>0并且D(v,u)>0这个对将正数贡献给总和 D(u,v)<0 。 由于没有负循环，所以D(u,v) + D(v,u) >= 0并且因此D(v,u) >= -D(u,v) 。 正如我们所见， D(v,u) + D(u,v)为求和贡献了一个非负数。 由于上述情况对于每一对u,v都是正确的u,v - 没有一对可以贡献负数，并且求和不能是负数。
QED
具有负边，但没有任何负循环，则D（u，v）上的Sigma（所有顶点对上的和）不能为负。
u -> v ，D（u，v）= 0 考虑有向图：
1 -> 2 -> 3
每个弧的成本为-1 ：没有负成本循环，但所有对的总和为负。 所以这个说法是错误的，因为我们找到了一个反例。
u -> v 在这种情况下，如果我们想找到一个反例，我们必须考虑一个在所有节点对之间都有路径的图，否则总和总是正的，因为我们将会添加一个无限数量。
考虑从节点x到节点y负成本路径。 那么从y到x的路径成本必须是正的，并且D(x, y) + D(y, x)不是负的，否则我们会有负循环，这是不允许的。
由于每个负成本路径必须具有正成本（返回路径+初始路径），因此对于这种情况，该陈述是正确的。
链接地址: http://www.djcxy.com/p/35265.html