我有一个带有起始节点S和结束节点E的图G.这个图的特殊之处在于,不是边缘有成本,而是具有成本的节点.我想找到S和E之间的方式(一组节点,W),以便最小化(W).(实际上,我对W不感兴趣,只是max(W))等价,如果我删除成本大于k的所有节点,那么最小的k是什么,以便S和E仍然连接？
我有一个想法,但想知道它是否正确和最佳.这是我目前的伪代码:
L := Priority Queue of nodes (minimum on top)
L.add(S, S.weight)
while (!L.empty) {
X = L.poll()
return X.weight if (X == G)
mark X visited
foreach (unvisited neighbour N of X, N not in L) {
N.weight = max(N.weight, X.weight)
L.add(N, N.weight)
}
}
我认为最坏的情况是O(n log n),其中n是节点数.
以下是我的具体问题(渗透)的一些细节,但我也对这个问题的算法感兴趣.节点权重在0和给定的最大值之间随机均匀分布.我的节点是在R²平面上的泊松分布,如果两个节点之间的距离小于给定的常数,则存在两个节点之间的边.可能有很多节点,因此它们是动态生成的(隐藏在伪代码中的foreach中).我的起始节点在(0,0)中,结束节点是距离(0,0)大于R的距离上的任何节点.
编辑:节点上的权重是浮点数.
这是一个消费税:
设G是具有n个顶点和m个边的加权有向图,其中所有边具有正权重.有向循环是一个有向路径,它在同一个顶点开始和结束,并包含至少一个边.给出O(n ^ 3)算法以找到G最小总重量的有向循环.将给出O((n ^ 2)*m)算法的部分信用.
这是我的算法.
我做了DFS.每当我找到一个back edge,我知道我有一个定向循环.
然后我会暂时沿着parent array(直到我穿过周期中的所有顶点)并计算出来total weights.
然后我将total weight这个周期与之比较min.min始终采用最小总重量.DFS完成后,我们也找到了最小的定向循环.
那么,关于时间的复杂性.
说实话,我不知道算法的时间复杂度.
对于DFS,遍历取O(m + n)(如果m是边数,则n是顶点数).对于每个顶点,它可能指向其祖先之一,从而形成一个循环.当找到一个循环时,需要O(n)来总结总重量.
所以我认为总时间是O(m + n*n).但显然这是错误的,如消费中所述,最佳时间是O(n ^ 3),正常时间是O(m*n ^ 2).
任何人都可以帮助我: