algorithm - 具有权重限制的图搜索

Question

我有一个无向的加权图，其中包含任意类型的对象作为节点。两个节点A和B之间的边的权重是这两个节点在区间(0, 1)中的相似度。相似度为0导致节点之间没有连接，因此图可能被划分。

给定一个目标权重 w 和一个起始节点 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's algorithm以及上述主张。

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)