ускорении работы дейкcтры на реальных больших графах с 12 сек до 0.002

lubanj

осторожно трафик!
http://logic.pdmi.ras.ru/midas/sites/default/files/midas-wer...
можно листать пэйдждауном, просматривая лишь картинки и сводные таблицы.
суть эвристик и препроцессингов примерно понятна
задрочили по самое небалуйся короче!

elenangel

(Times on 2.4-GHz AMD Opteron with 16 MB of RAM.)

salamander

ускорении работы дейкcтры на реальных больших графах с 12 сек до 0.002

Там вообще несколько другая задача рассматривается. Они (многократно) ищут кратчайший путь между парами заданных вершин (x_i, y_i а не расстояния от заданной вершины a до всех остальных, как в алгоритме Дейкстры.

можно листать пэйдждауном, просматривая лишь картинки и сводные таблицы

А, ну тогда понятно...

salamander

Я спрашивал людей, которые там были. Они решили, что имелось ввиду GB, и отвлекать лектора по этому поводу вопросом не стоит.

Anturag

Не прошло и года Более года назад эта тема была публично раскрыта Андреем Голдбергом на лекции в CS клубе при ПОМИ.