Jets's blog

By Jets, 4 years ago, translation, In English

What is the fastest priority queue for Dijkstra with integer positive weights in practice?

Judging by the asymptotics, Fibonacci heap and Brodal queue look best, but in practice they have a big constant.Wiki It’s clear that the usual std::priority_queue is enough for problems, but I'm interested the best in performance.

Judging by these tests, Binary heap better in all operations.

Found another such queue HOT queue.

  • Vote: I like it
  • +1
  • Vote: I do not like it