3

I implemented Dijkstra's path finding algorithm in JavaScript and a big part of it involves storing the distances to nodes and fetching the smallest. The distances change often and the smallest is fetched a lot.

I'm currently using an Ordered Linked List, with items being put in order when added.

Is there a faster way?

Edits:

Update:

Implemented arnaud's suggestion of a Fibonacci Heap. It was 32 to 85 times faster with diminishing returns the larger the dataset.

I deviated from the true Fibonacci Heap by not running consolidate every time a value was removed. I found running it once every 50 shifts performed best.

Source Code is here: https://github.com/nojacko/dijkstras-js/blob/bda68d1274629c30b1f902ffb7f95f1e3c695973/Dijkstras.js

  • 1
    How big is the list? – Dan Pichelman Feb 17 '15 at 15:06
  • 1
    You almost certainly want a skip list. – ggovan Feb 17 '15 at 15:30
  • 4
    Min priority queue, implemented as a Fibonacci heap, as described at the beginning of the Wikipedia article: en.wikipedia.org/wiki/Dijkstra%27s_algorithm. And what do you think: if someone who is asking here a question does not even look into Wikipedia, should he get a downvote for lazyness ;-)? – Doc Brown Feb 17 '15 at 15:32
  • 4
    Be careful with the term "ordered." Sometimes it indicates "in the order data was added" like a simple queue, append-to-the-end list, OrderedDict, etc. Sometimes it means "sorted" or "ordered according to some criteria," which includes sorted lists, heaps, etc. This later sense is inherently more expensive because you have to do something more than "add one on" to maintain the ordering criteria. – Jonathan Eunice Feb 17 '15 at 15:50
  • @DanPichelman Almost any size. My usage would be likely be 50,000-100,000. – James Jackson Feb 17 '15 at 18:51
6

If it is truly an ordered linked list, this should be a fairly bad choice because you have to traverse the list one by one until you find the right place to insert the item. In other words O(N). This is ok if the list is small but can get out of hand for big graphs.

Usually, what you will need for that kind of stuff is a heap:

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

...where you can insert and pop in O(log(n)) ...it's also usually available out of the box in most programming languages.

  • Thanks. Linked list was the best I could think of when I needed it. That had a massive (and expected) speed improvement over Array.sort() that I originally used to get Dijkastra's working ASAP. – James Jackson Feb 17 '15 at 19:00
  • @JamesJackson there is an ordered linked list structure that has a tree imposed on top of it for fast (O(log n)) lookup. This is the skip list mentioned in comments above. While a simple linked list is less than ideal for substantial sized lists, the skip list is much better (and its easier to reason about). An implementation of this in JavaScript can be found at github.com/ceejbot/skiplist – user40980 May 12 '15 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.