有个一个有向图G=(V,E)，同时给定各点的一个权P(v). 要求找出每个点能达到的最相似节点。也就是说对所有的u, 找到所有的能达到的v使得|P(u)-P(v)|最小。u能达到v表示存在一条路径能连接u到v

我能想到的算法是收圈，做拓扑排序搞出一个树来，然后从地下往上面推。一个点的子树必然是能到达的点。但是怎么最快的找到最相似点呢？维护一个有序的结构不便宜，至少也是和子树大小线性。这样复杂度就是O( E+V^2 )了。。

当然可能我的算法就不对。望不吝赐教

• 顶顶 (0) usfish 2009-11-16 22:56:30