Как быстро найти узел графа имеющий минимальное расстояние до любого другого?

покажешь как?

если нет отрицательных циклов, то можно и с квадратичной. но в оп-посте об этом ни слова.

Лол, решается с линейной сложностью, погромист ты наш.

Ты ничего не понимаешь в алгоритмах на графах. Прекрати умничать на ЛОРе.

Насколько я знаю, ничего лучше, чем Дейкстра для каждой вершины, тут не придумали. Ну или поиска в ширину для каждой вершины, если граф не взвешенный.

Да я, идиот, сдуру решил, что у ОПа дерево, там-то как раз центр отсечением листьев за линейное время находится, но в общем случае с графами это, конечно же, не так.

Да я, идиот, сдуру решил, что у ОПа дерево, там-то как раз центр отсечением листьев за линейное время находится, но в общем случае с графами это, конечно же, не так.

кстати можно найти мин.остовное дерево графа и уже в нём искать центр. Всяко быстрее поиска маршрутов по Дейсктре/Флойду, логарифмическая сложность против степенной.

только если доказать что «центр» дерева будет «центром» графа, что в принципе похоже на правду.

Для произвольного минимального остовного дерева это утверждение не выполняется:

1-2-3-4
| |
5-6-7

Центр графа - вершина 2, если убрать ребро 2-6, тогда центром получившегося дерева будет вершина 1

Как правильно пока сказал один человек в треде, это поиск центра: https://en.wikipedia.org/wiki/1-center_problem

Однако по ссылке, что он дал, не предлагают интересного алгоритма. Мол, берите Floyd-Warshall и наслаждайтесь. В общем случае похоже, что так и следует делать. Разве что учесть, что для разного типа графов есть разные подходящие алгоритмы по поиску кратчайших путей всех со всеми (например, Johnson для разреженных).

В случае положительных рёбер можно действительно применять всеми любимого Dijkstra. И тут уже можно разыграться, поскольку при формулировке решения через Dijkstra задача принимает ярко выраженный минимаксный характер.

Ищем же min_i(max_j(d(i, j)), где d(i, j) решается Dijkstra'ой. Поэтому много элементов из матрицы расстояний можно будет смело не искать, базируясь на уже рассмотренных элементах. Для вдохновения можешь глянуть минимаксные алгоритмы типа alpha-beta pruning.

дейкстра не для каждого графа работает

Да тут много смешных глупостей наговорили все подряд.