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

Claims on shortest path between two node in graph?

如果加权有向图G（可能有负边）上两个顶点之间的最短路径由D(u, v)表示，则以下说法总是错误的。

with having negative edges, but didn't have any negative cycle, then Sigma on D(u,v) (sum on all vertex pairs) cannot be negative.

Why this claims is False?

what is D(u,v) where there's no path from u to v is not given in my notes, but I think D(u,v)=0 in this case.

with having negative edges, but didn't have any negative cycle, then Sigma on D(u,v) (sum on all vertex pairs) cannot be negative.

  1. D(u, v) = 0 无弧 u -> v

考虑有向图：

1 -> 2 -> 3

每条弧都有成本-1：没有负成本循环，但所有对的总和为负。所以这个说法是错误的，因为我们找到了一个反例。

  1. D(u, v) = infinity 无弧 u -> v

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

考虑从节点 x 到节点 y 的负成本路径。那么从 y 到 x 的路径成本必须是正的，这样 D(x, y) + D(y, x) 就不是负的，否则我们就会有一个负循环，这是不允许的。

由于每条负成本路径都必须具有正成本（return 路径 + 初始路径），因此对于这种情况，该陈述是正确的。

假设 D(u,v) = infinity 如果没有从 u 到 v 的路径（我真的认为没有理由不这样假设，假设 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 - 没有对可以贡献负数，求和不能为负。

QED