algorithm - How to find the common nearest neighbour vertex of given k different vertices in an undirected weighted graph? -

given undirected weighted graph g(v,e). , 3 vertices let u, v , w. find vertex x of g. such dist(u,x) + dist(v,x) + dist(w,x) minimum. x vertex in g (u, v , w included). there exits particular algorithm problem?

you can stack algorithm pseudo-code below:

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 node 1                 }                 else if(isgraphprocessed[neigh.id] == 2) // flag of node 2 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 node 2                 }                 else if(isgraphprocessed[neigh.id] == 1) // flag of node 1 set                     return neigh;         nodes2 = tmp;     }     return null; // don't exist } 

how work

• you start both edges of graph
• you check neighbors in stack
• if neighbor have been added in stack of other node, mean have been reached other node --> closest node. return it.
• if nothing found, same thing neighbour of neigbors (and on recursively) until found.
• if node2 can't reached node1 returns 0.

note : algorithm works find minimal distance between 2 edges. if want 3 edges can add 3rd stack , first node having 3 flags (e.g. 1, 2 , 4).

hope helps :)