Поиск узла, который имеет наименьшее максимальное расстояние до всех других узлов в графе с использованием BFS?

Question

Я сделал эту функцию несколько дней назад, чтобы найти диаметр графа с помощью BFS:

dist[v] = 0; 
queue<int> next; 
next.push(v); 

int bdist = 0; //biggest distance 
while(!next.empty()) { 
    int pos = next.front(); 
    next.pop(); 
    bdist = dist[pos]; 

    for(int i = 0; i < graph[pos].size(); ++i) { 
     int nghbr = graph[pos][i]; 
     if(dist[nghbr] > dist[pos]+1) { 
      dist[nghbr] = dist[pos]+1; 
      next.push(nghbr); 
     } 
    } 
} 

return bdist-1; 
} 

Как/что я могу изменить в коде, так что вместо того, чтобы вернулся диаметр, я вместо того, чтобы получить вернулся узел который имеет наименьшее максимальное расстояние до всех остальных узлов? Как будет выглядеть новый код?

Answer 1

В основном вы вызываете функцию most_dist для каждого узла (также я думаю, вы должны вернуть bdist not bdist-1). Таким образом, для каждого узла вы получаете расстояние от максимального узла от этого узла. Так вот псевдокод, чтобы получить узел с минимальным максимальным расстоянием

 /*g is your graph */ 
    /* This code goes in your main */ 
    /* assuming 0 based indexing of nodes */ 
    answer = 0 /* stores your answer, let node 0 be the answer we will update it */ 
    dis = biggest_dist(0,g) /* stores the maximum distances of node 0 */ 
    for each node 
      maxdist = biggest_dist(node,g) 
      if maxdist < dis: 
       dis = maxdist 
       answer = node 

    print answer /* your answer */ 

Помните, что может быть более одного ответа, это выводит любой один из них. Также, как было предложено другими, вы должны отредактировать свой вопрос, чтобы отразить ваши усилия.
РЕДАКТИРОВАТЬ
Этот алгоритм имеет сложность O (EV + V^2). Если вы используете floyyd warshall для вычисления кратчайших расстояний между всеми, от которых вы легко получите свой ответ, это будет O (V^3) и с использованием dijakstra's будет O (EV + V^2logV). Теперь, как и на простом графике E может при max быть V^2 Я бы выбрал алгоритм, данный вами, если мне нужно уменьшить временную сложность.