我们有一个关于带正边和负边的加权无圈图G(V, E)的码。我们用下面的代码来改变这个图的权重,给出一个没有负边(G')的(G')。如果V={1,2...,n}和G_ij是边i到边j的权重。
Change_weight(G)
for t=1 to n
for j=1 to n
G_i=min G_ij for All K
if G_i < 0 (we have a bar on G)
G_ij = G_ij+G_i for all j
G_ki = G_ki+G_i for all k
我们有两
下图是我在接受三星采访时被问到的问题。我不得不写程序来找出我和M之间的最小距离,还有一个额外的约束条件,我们可以改变其中一条边。例如,可以移动边FM以连接边L和M,边值仍为4。
如果您注意到,通过I-> E -> F -> G -> M,I和M之间的距离是20。但是,如果我们更改其中一条边,使L到M的边值现在为4。我们现在必须移动edge FM来加入L和M。通过这种方法,I和M之间的距离是20。
一条任意的边u,v可以改成u,t或t,v,但不能改成x,y,所以边上的一个顶点必须是相同的。
请找到下面的图片来说明该场景-
所以我的问题是我必须为此编写程序。为了找
我一直在研究加权有向图的图算法,特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。
设G是一个具有节点{1,…,n}和邻接矩阵A的加权有向图。设B_k i,j是从i到j的最短路径,它使用中间节点<= k。
input A
if i = j then set B[i, j] = 0
set B[i, j] = 0
else if i != j && there is an arc(i, j)
set B[i, j] = A[i, j]
else
set B[i, j] = infinity
#B = B0
for k = 1 to n:
这个问题来自CodeEval开放挑战,我确实尝试了很多方法来更快地解决这个问题,但结果就是“超时”。指向该问题的链接如下:。那么我的解决方案如下:
import sys
import profile
import array
import collections
def main():
with open(sys.argv[1], "r") as f:
for line in f.readlines():
data = line.strip().split('; ')
src, dst