Кратчайшее расстояние между всеми вершинами - Помощь студентам

ooooch · 15.11.2009, 14:10

нужно найти кратчайшее расстояние между всеми вершинами
сразу приходит в голову алгоритм Флойда

, но количество вершин <=100000 и матрица такого рамера будет превышать лимит по памяти....
как быть?

LeBron · 15.11.2009, 14:12

Можно полное условие задачи? А то сдесь матрица матрицой, если тупой Флойд, то оно зависнет по времени, память это второстепенное. Есть ограничение на количество ребер?

ooooch · 15.11.2009, 14:54

ребра тоже <=100000

LeBron · 15.11.2009, 15:06

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

ooooch · 15.11.2009, 15:24

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

хммм...а что потом со списком ребер делать то?

LeBron · 15.11.2009, 15:36

Ну теперь хоть кажеться понятным, что от нас требуют. Только один вопрос (может, все еще проще, чем я думаю) - что потом делать с результатами? Ведь мы получим кратчайшие расстояния от 100000 вершин до 100000 вершин, тоесть 10 миллиардов чисел

Нужно найти все эти 10 миллиардов результатов? обычно требования в таких задачах другие. Если именно так, то я не представляю, как решать, ведь алгоритмы, которые не загибаються на стадии обработки (и фактически являються верными в таких случаях) просто упадут при сохранении результатов. Если нету закономерности в результатах, то это невозможно сделать, так как придеться потратить 10 Гб, что бы хранить в процессе решения результаты. Можете написать джадж-систему и номер задачи, я сам посмотрю?

15.11.2009, 14:10	#1
ooooch Регистрация: 15.11.2009 Сообщений: 4	Кратчайшее расстояние между всеми вершинами нужно найти кратчайшее расстояние между всеми вершинами сразу приходит в голову алгоритм Флойда, но количество вершин <=100000 и матрица такого рамера будет превышать лимит по памяти.... как быть?

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Расстояние между раммкой	Syltan	Microsoft Office Word	1	14.11.2009 20:31
Расстояние между строками	Kib	Общие вопросы Delphi	5	30.06.2009 01:02
Расстояние между абзацами в CSS	Андрей79	HTML и CSS	4	13.04.2009 09:59
max расстояние между плоскими телами!	Flanker13	Общие вопросы Delphi	3	17.03.2009 13:46
Расстояние между 2 городами	Uli9	Помощь студентам	1	06.12.2008 22:40

15.11.2009, 14:12	#2
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Можно полное условие задачи? А то сдесь матрица матрицой, если тупой Флойд, то оно зависнет по времени, память это второстепенное. Есть ограничение на количество ребер?

15.11.2009, 14:54	#3
ooooch Регистрация: 15.11.2009 Сообщений: 4	ребра тоже <=100000

15.11.2009, 15:06	#4
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Если так, то задача довольно простая, если бы небыло ограничения на ребра - то задача мне кажеться теоретически неразрешимой. Значит так: оформляем граф не ввиде матрицы смежности, а в виде списков ребер. А путь дальнейшего решения зависит от самого графа. Еще несколько уточняющих вопросов от меня (хочеться наконец полносьтю увидеть условие задачи) - граф ориентированный? есть ли упоминания об наличии/отсутствии циклов, циклов отрицательного веса, петель, мультиребер?

15.11.2009, 15:24	#5
ooooch Регистрация: 15.11.2009 Сообщений: 4	граф неориентированный петель нет вес ребер равен 1 гарантируется, что из каждой вершины можно попасть в каждую вроде как все хммм...а что потом со списком ребер делать то?

15.11.2009, 15:36	#6
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Ну теперь хоть кажеться понятным, что от нас требуют. Только один вопрос (может, все еще проще, чем я думаю) - что потом делать с результатами? Ведь мы получим кратчайшие расстояния от 100000 вершин до 100000 вершин, тоесть 10 миллиардов чисел Нужно найти все эти 10 миллиардов результатов? обычно требования в таких задачах другие. Если именно так, то я не представляю, как решать, ведь алгоритмы, которые не загибаються на стадии обработки (и фактически являються верными в таких случаях) просто упадут при сохранении результатов. Если нету закономерности в результатах, то это невозможно сделать, так как придеться потратить 10 Гб, что бы хранить в процессе решения результаты. Можете написать джадж-систему и номер задачи, я сам посмотрю?