Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Технологии > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 15.11.2009, 15:10   #1
ooooch
 
Регистрация: 15.11.2009
Сообщений: 4
По умолчанию Кратчайшее расстояние между всеми вершинами

нужно найти кратчайшее расстояние между всеми вершинами
сразу приходит в голову алгоритм Флойда, но количество вершин <=100000 и матрица такого рамера будет превышать лимит по памяти....
как быть?
ooooch вне форума Ответить с цитированием
Старый 15.11.2009, 15:12   #2
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Можно полное условие задачи? А то сдесь матрица матрицой, если тупой Флойд, то оно зависнет по времени, память это второстепенное. Есть ограничение на количество ребер?
LeBron вне форума Ответить с цитированием
Старый 15.11.2009, 15:54   #3
ooooch
 
Регистрация: 15.11.2009
Сообщений: 4
По умолчанию

ребра тоже <=100000
ooooch вне форума Ответить с цитированием
Старый 15.11.2009, 16:06   #4
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

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

граф неориентированный
петель нет
вес ребер равен 1
гарантируется, что из каждой вершины можно попасть в каждую
вроде как все
хммм...а что потом со списком ребер делать то?
ooooch вне форума Ответить с цитированием
Старый 15.11.2009, 16:36   #6
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

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

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Расстояние между раммкой Syltan Microsoft Office Word 1 14.11.2009 21: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 14:46
Расстояние между 2 городами Uli9 Помощь студентам 1 06.12.2008 23:40