Здравствуйте!
Подскажите, пожалуйста, если кто в курсе, где можно посмотреть код такой реализации Дейкстры, у кого-нибудь есть ссылка? Насколько оправдано применение Фибоначчиевой пирамиды на практике? Т.е. заметно ли ускорение по сравнению с реализацией Дейкстры с обычным heap-ом? В теории понятно, что O(E + N * logN) лучше, чем O(E * logN), вопрос насколько велика скрытая константа.
Спасибо!
Я в свое время слышал про бенчмарки фибоначчиевой кучи из Boost'а, сейчас вбил в гугл "boost fibonacci heap dijkstra", по первой ссылке есть сравнение. Кажется, применимость оной штуки правда весьма сомнительная (учитывая, что для очень плотных графов есть всем известная и невероятно быстрая реализация за O(V2 + E) без каких-либо куч).
Если я не ошибаюсь, то Фибоначчиева куча действительно почти не используется из-за большой константы.
Вместо неё используют Pairing heap не так уж сильно теряя в асимптотике, но константа действительно гораздо лучше.
Спасибо, почитаю обязательно. А есть какой-нибудь не сильно замороченный алгоритм поиска кратчайших путей от одной вершины до всех за O(E) (стоимости ребер — произвольные неотрицательные вещественные числа)?
Таки Radix Heap — единственное, что я знаю помимо Фибоначчиевой и она, кажется, использует целочисленность.
В этой статейке написано, что есть много разных таких дейкстр, но мне, честно говоря, лень гуглить :]
http://keithschwarz.com/interesting/code/?dir=dijkstra