在图中两个节点之间的最短路径的声明？

Question

3

如果在加权有向图 G 中，两个顶点之间的最短路径（可能存在负权边）由 D(u, v) 表示，则以下声明总是不正确的。

即使具有负权边，但没有任何负环的情况下，D(u,v)（所有顶点对之和的总和）也不能为负。

Why this claims is False?

在我的笔记中没有给出从u到v没有路径时D(u,v)是什么，但我认为在这种情况下D(u,v)=0。

- user4737480

如果从u到v没有路径，通常会表示为D(u,v) = 无穷大，但这取决于定义。 - amit

如果我们使用无穷大，这个语句可能是正确的吗？@amit，可以吗？ - user4737480

我不确定，我可以尝试证明或找到反例，但这取决于这个问题的答案。如果在u-v之间没有路径的情况下D(u,v)=0，那么只有负权重边的DAG显然符合要求，但这对我来说似乎是奇怪的假设。 - amit

请考虑两种情况，通过回答 @amit 进行。 - user4737480

2个回答

1

如果有负边但没有负环，则D(u,v)（所有顶点对的总和）不可能为负数。

考虑有向图：

1 -> 2 -> 3

每个弧的成本都为-1：没有负成本环，但所有对之和是负数。因此，这个命题是错误的，因为我们已经找到了一个反例。

如果没有弧u -> v，则D(u, v) = infinity。

在这种情况下，如果我们想要找到一个反例，我们必须考虑一个具有所有节点对之间路径的图，否则总和将始终为正值，因为我们将添加无限数量。

考虑从节点x到节点y的负成本路径。然后，从y到x的路径成本必须为正，并且D(x, y) + D(y, x)不能为负，否则我们将有一个负循环，这是不允许的。

由于每个负成本路径必须具有正成本（返回路径+初始路径），因此该语句对于此情况为真。

- IVlad

1

D(3,1) = 无穷大，因此所有D(i,j)的总和不是负数。（但它是无穷大，也就是非常正的数）。 - amit

假设如果没有路径=无穷大或0？我们如何证明？ - user4737480

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

假设如果从u到v没有路径，那么D(u,v) = infinity（我真的没有理由做其他假设，在这种情况下假设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都成立，因此没有一对可以对总和造成负面影响，总和也不能为负数。

证毕。