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