如何在一个无向赋权图中找到给定k个不同顶点的公共最近邻顶点？

Question

给定一个无向赋权图G(V，E)。求G的一个顶点x，使得dist(u，x) + dist(v，x) + dist( w，x)是最小的。X可以是G中的任何顶点(包括u、v和w)。对于这个问题有什么特别的算法吗？

Answer 1

你可以使用堆栈算法来实现，就像下面的伪代码：

void FindNeigh(node node1, node node2,int graphsize)
{
    byte[graphsize] isGraphProcessed; // 0 array

    stack nodes1, nodes2; //0 arrays
    nodes1.push(node1);
    nodes2.push(node2);
    bool found = false;

    while(!nodes1.empty && !nodes2.empty())
    {
        stack tmp = null;
        for(node: nodes1)
            for(neigh : node.neighbors)
                if(!isGraphProcessed[neigh.id])
                {
                    tmp.push(neigh.id);
                    isGraphProcessed[neigh.id] = 1; // Flags for node 1
                }
                else if(isGraphProcessed[neigh.id] == 2) // The flag of node 2 is set
                    return neigh;
        nodes1 =tmp;
        tmp = null;
        for(node: nodes2)
            for(neigh : node.neighbors)
                if(!isGraphProcessed[neigh.id])
                {
                    tmp.push(neigh.id);
                    isGraphProcessed[neigh.id] = 2; // Flags for node 2
                }
                else if(isGraphProcessed[neigh.id] == 1) // The flag of node 1 is set
                    return neigh;
        nodes2 = tmp;
    }
    return NULL; // don't exist
}

它是如何工作的

如果一个邻居已经被添加到另一个节点的堆栈中，这意味着它已经被另一个节点到达了-->

• 。我们返回它。
• 如果什么都没有找到，我们会对邻居的邻居做同样的事情(以此类推)，直到找到什么为止。
• 如果无法从node1访问到node2，则返回0。

注意:此算法用于找到两条边之间的最小距离。

希望它能有所帮助:)

Answer 2

如果k很大，并且没有负边成本周期，那么Floyd Warshall的算法可以工作。它在O(|V|^3)时间内运行，完成后，我们得到了整个最短距离矩阵，我们可以在O(1)时间内得到任意两个顶点之间的最短距离。然后，只需扫描并查找与k顶点的总距离值之和最小的最佳顶点x。