带权重限制的图搜索

Question

我有一个无向的加权图,其中任意类型的对象作为节点.两个节点A和B之间的边缘的权重是这两个节点在区间(0,1)中的相似性.相似度0导致节点之间没有连接,因此可以对图形进行分区.

给定目标权重w和起始节点S,起始节点S是用于找到权重> w的所有节点的算法.子节点(从S看)应该具有路径上所有权重的乘积.即:

S --(0.9)-- N1 --(0.9)-- N2 --(0.6) -- N3

从S开始,节点将具有以下相似性值:

N1: 0.9 
N2: 0.9 * 0.9 = 0.81
N3: 0.9 * 0.9 * 0.6 = 0.486

因此,给定S和目标权重0.5,搜索应该返回N1和N3.从N2开始的搜索将返回S,N1和N3.

他们的算法是否符合我的需求？

Answer 1

请注意以下事项:

1. log(p1 * p2) = log(p1) + log(p2)
2. 如果p1 < p2那时log(p1) < log(p2)因此:-log(p1) > -log(p2)

声明[基于上面提到的1,2]:找到从s到t最相似的路线,实际上是找到从s到t的最小路径,其中权重是-log原始的.

我建议基于Dijkstra算法和上述声明的以下算法.

1. define for each edge e: w'(e) = -log(w(e)) //well defined because w(e) > 0
2. run Dijkstra's algorithm on the graph with the modified weights.
3. return all vertices v that their weight is dijkstra(v) < -log(needed)