图形上的代码输出以及本地竞赛的某些声明?

2015-05-06 c++ algorithm data-structures graph graph-theory

我遇到了如下问题:

我们有一个带有正负边的加权无环图G(V, E)的代码。我们改变该曲线图的重量与下面的代码,得到G无负边缘(G')如果V={1,2...,n}并且G_ij是边i到边j的权重。

Change_weight(G) 
 for i=i to n   
   for j=1 to n
      c_i=min c_ij for all j
      if c_i < 0 
          c_ij = c_ij-c_i  for all j
          c_ki = c_ki+c_i  for all k

我们有两个公理:

1)G中每两个顶点之间的最短路径与G'相同。

2)G中每两个顶点之间的最短路径长度与G'相同。

我们要验证这两个句子。哪个是正确的,哪个是错误的。谁可以添加一些提示,说明这些原因是对还是错?

我的解决方案:

我认为两个是错误的,如下面的反例所示,原始图形在左侧给出,并且在算法运行后,结果在右侧是从1到3改变的最短路径,它是从顶点2传递的,但是在算法运行之后它从未从顶点2传递出去。

Answers

假设:

您对问题的陈述存在一些问题;我做了一些假设,在这里我将予以阐明。鉴于这些假设是正确的,您的问题的答案在以下部分中。

首先 ,正如@amit所说,您对j的使用不清楚。看来您的意思是这样的:

Change_weight(G)
  for i = 1 to n   
    c_i = min(c_ij)  for all j
    if c_i < 0 
      c_ij = c_ij-c_i  for all j
      c_ki = c_ki+c_i  for all k

也就是说,对于每个顶点i ,如果最小输出边缘c_i为负,则将所有输出边缘的权重增加-c_i并将所有输入边缘的权重减小-c_i 。然后最小的输出边缘的权重为0。

其次该算法本身不能保证G'没有负边!考虑下图:

拓扑排序的图形破坏了算法Change_weight(。)

此处,边(1,2)的值通过对1的操作被上推为0,但通过对2的操作被推回-1。您必须指定图的拓扑顺序相反,以便边(i,j)始终由j操作,然后再由i操作。 (或者,您可以按拓扑顺序对其进行排序,并从n to 1迭代n to 1


回答您的问题:

1) G每两个顶点之间的最短路径与G'相同。

这是真的。将路径不视为边的元组,而是节点的元组。对于顶点st ,路径是节点(s, v_1, v_2, ..., t)的元组,其中每两个后续元素之间都有一条边。对于每个顶点uu降低进入边缘的成本的速度与增加出边缘的成本的速度相同;因此,在路径中包含u的相对成本不变。

2) G每两个顶点之间的最短路径的权重与G'的权重相同。

这是错误的。源s将其输出权重增加-c_s ,而目的地t将其输入权重减少-c_t 。如果c_s != c_t ,则路径的权重将不同。

重申一下,从st的每条路径的权重将增加(c_t-c_s) 。因此,给定st对的最短路径仍将是最短的(因为该对之间的所有路径都以相同的量变化)。但是,重量显然不必相同。

Related