Тема: Диаметр графа
Как находить диаметр взвешенного графа?
Re: Диаметр графа
а какая разница взвешенный или нет?
ну самое тупое -- V BFS'ов
Re: Диаметр графа
вы бы ограничения дали 
Re: Диаметр графа
Есть замечательный алгоритм Флойда-Уоршалла. Работает за O(N^3), реализация занимает 3 строки.
Re: Диаметр графа
chum пишет:
а какая разница взвешенный или нет?
ну самое тупое -- V BFS'ов
Есть разница ... Если у нас граф с рёбрами стоимостью 1, то тут да очередь обычная, а если взвешенный то тут не выгодно писать очередь, она может много раз ложить одну вершину .. Придётся писать V дейкстр с кучей ^^
6 2010-04-15 08:31:57 Отредактировано chum (2010-04-15 08:32:41)
Re: Диаметр графа
brainail пишет:
chum пишет:а какая разница взвешенный или нет?
ну самое тупое -- V BFS'овЕсть разница ... Если у нас граф с рёбрами стоимостью 1, то тут да очередь обычная, а если взвешенный то тут не выгодно писать очередь, она может много раз ложить одну вершину .. Придётся писать V дейкстр с кучей ^^
конечно же нет разницы!
Материал из Википедии — свободной энциклопедии
Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер, которые необходимо пройти, чтобы добраться из одной вершины в другую.
какие дейкстры с флойдами?))
V обходов в глубину / ширину!
Re: Диаметр графа
Аааа, тогда да.
Я же подумал что человек хочет узнать диаметр, если рёбра взвешены, и уже считается не по кол-ву рёбер, а по длине пути! извиняюсь.
Re: Диаметр графа
Кстати, наверняка человек это и имел ввиду иначе зачем он указал что граф взвешенный. При взвешенном графе, если конечно вес = длина ребра, диаметр считается по длине пути.
Re: Диаметр графа
Ну тогда если так, то не БФС, а Дейкстра с кучей
Re: Диаметр графа
brainail пишет:
Ну тогда если так, то не БФС, а Дейкстра с кучей
Почему именно с кучей? Она ведь не всегда работает быстрее Если ребер много, то проще уже писать Флойда - будет работать быстрее чем N Дейкстр с кучей и писать намного быстрее.
Re: Диаметр графа
KADR пишет:
brainail пишет:Ну тогда если так, то не БФС, а Дейкстра с кучей
Почему именно с кучей? Она ведь не всегда работает быстрее
Конечно согласен! Просто условия не вижу вот и говорю что по ассимптотике лучше Но не всегда! 
Интересно, а вот фибоначива куча, она ведь за O(1) большинство операций делает, и ведь тогда дейкстра будет работать за O(V + E) :-D Я никогда её не писал, но если кто писал, как она себя ведёт при работе на больших тестах?
Re: Диаметр графа
brainail пишет:
KADR пишет:brainail пишет:Ну тогда если так, то не БФС, а Дейкстра с кучей
Почему именно с кучей? Она ведь не всегда работает быстрее
Конечно согласен! Просто условия не вижу вот и говорю что по ассимптотике лучше
Интересно, а вот фибоначива куча, она ведь за O(1) большинство операций делает, и ведь тогда дейкстра будет работать за O(V + E) :-D Я никогда её не писал, но если кто писал, как она себя ведёт при работе на больших тестах?
ээм
но мы же изменяем в куче элементы
а изменение стоит O(logN)
вообще дейкстру с фенвиком проще всего писать
Re: Диаметр графа
ээм
но мы же изменяем в куче элементы
а изменение стоит O(logN)вообще дейкстру с фенвиком проще всего писать
На С++ есть priority_queue. Всегда писал с ней и нормально работало А Фенвика еще нужно руками писать. Хоть там кода мало, но все равно занимает время.
Re: Диаметр графа
Куча рулез ^^