Здравствуйте.

Собственно задача:

Имеется сильно связный неориентированный невзвешенный граф. Требуется найти такую вершину (центр), чтобы кратчайшие расстояния от нее до всех остальных вершин графа были, по-возможности, минимальны.(по-моему не совсем корректно, поэтому скажу иначе: поиск в ширину, пущенный от нее, должен сделать минимальное число "волн").

Естественно, решение за O(n^2) очевидно (просто серия из n поисков в ширину), но при этом время работы алгоритма слишком велико. Собственно, был бы рад любым идеям по реализации данного алгоритма .

ЗЫ
Из собственных мыслей:

1.) Взять произвольную вершину. Пустив bfs из нее, найти наиболее удаленную от нее вершину ( пусть она будет называться L ). Пустив bfs от L, найти наиболее удаленную от нее вершину ( R ). Пустить одноременно два bfs'а от L и R и ждать их пересечения. Центр, имхо, будет лежать где-то в множестве вершин, вошедших в это пересечение. (но опять - таки их слишком много)

2.) Попытаться использовать данные предыдущих поисков. Но эта идея по-моему бесперспективна...

Неужели ни у кого нет никаких идей? Может условия задачи невнятно сформулировал?

Условие-то понятно, просто графы - это вообще не самая приятная тема.

Какой же у тебя граф, если на нем O(n²) слишком долго работает? В принципе и поиск центра орграфа (Флойд + минимальный эксцентриситет), который имеет сложность O(n³), отрабатывает довольно быстро. Никогда не сталкивался с тем, что "время работы алгоритма слишком велико".

Можно посмотреть на твой граф (хотя бы приблизительно, количество вершин чему равно?).

Даже когда известны ВСЕ расстояния между всеми вершинами, возможно ли определить центр по этой матрице расстояний меньше, чем за квадрат?
А вообще, тут, видимо, важно не только кол-во вершин в графе, но и кол-во рёбер.
Гы, http://forum.sources.ru/index.php?showtopic=225018

Количество вершин невелико(порядка тысячи). Дело в том, что время работы ограничено двумя секундами (а при этом имеются еще и некоторые подготовительные операции).



В том-то и дело, что мне нужно придумать алгоритм, который не будет считать расстояния между всеми вершинами.

Вообще, мне кажется, из того, что граф неориентированный и невзвешенный вытекает то, что значения минимального эксцентриситета для двух смежных вершин не будут различаться больше, чем на единицу. Исходя из этих соображений, я написал поиск, который, начиная с какой-то случайной вершины, идет по смежным вершинам с минимальным эксцентриситетом подобно поиску в глубину(причем я обрываю его по достижениии какого-то предельного числа ходов). Но опять-же при заданных временных ограничениях он не находит правильного ответа. Почему так происходит, я не понимаю (предельное число ходов - около 800, при этом, имхо, можно несколько раз пересечь граф по диаметру).

> время работы ограничено двумя секундами

СТОП. Это для олимпиады? Тогда мы не будем помогать.

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

Во-первых, Дейкстра - он. И алгоритм, кстати, - тоже.
Да и в придумывании велосипедов (особенно для олимпиады) ничего плохоого нет. Я, например, и придумал и написал несколько реализаций "Дейкстры" до того, как узнал, что этот алгоритм, оказывается, имеет имя собственное (причем, что самое обидное - не мое .

Если это задача с реальной олимпиады, в которой ты в данный момент участвуешь, то думай сам.
Если это с какой-то давно прошедшей, то тогда да, попробуем помочь.

Возможно, алгоритм Дейкстры не самый удачный пример)) Ну да ладно...



О'кей, буду думать)