Fastest javascript implementation of Dijkstra's algorithm?

Question

JavaScript

Given a weighted graph. It is necessary to solve 2 problems: find the lengths of paths to all points from the starting point and also get the shortest (cheapest, optimal, etc.) path from one point to another.

Dijkstra's algorithm suggests itself logically.

BUT!

The implementation needs to be fast.
For evaluation: for 160 vertices and 350 edges, running in 3 milliseconds is slow.

I tried to find JavaScript implementations of this algorithm on the Internet. However, either they were too slow,
such as this one
or this one

. Or they did not work correctly, i.e. looped even though the input was valid
like this

I am also attaching an example here with ~160 vertices and ~350 edges, so that you don’t have to come up with such an example yourself in order to measure time

Link to an example of such a graph

If you can somehow optimize those implementations, links to which I attached above, and from these optimizations they will quickly work, I will also be very grateful!

Answer 1

Try rewriting with fixed length arrays. In all implementations, according to your links, the vertices are numbered by lines and a bunch of arrays of type distance and visited are actually dictionaries, or as it is called in js. This is much slower than a dumb array numbered from 0 to n.
You will need one dictionary to renumber vertices into numbers. Then convert the garf to an array of arrays instead of this complex object.
And already on it drive a dijkstra. It should at least speed up a couple of times. And even in all 10.

Answer 2

Option 1:
You can implement it yourself in js, but do not use those features that reduce performance.
Option 2:
Implement the algorithm in Rust and compile the code under wasm.
For example, there is such a lib: https://crates.io/crates/pathfinding , which can be used for this

Answer 3

Why Javascript? In terms of time, 3-4ms is nothing for an interpreted language (ran the code in the browser console from the first link). There are strange things that can be fixed, for example, this `if (String(child) === String(startNode))`, or do fewer operations with arrays, or allocate a fixed size to them in advance to avoid pushes and dynamic memory allocation . If you understand the algorithm, then you can run through the code and look for moments where you can discard unnecessary iterations.

Answer 4

Write in C/C++ and compile with wasm. With a high degree of probability, the speed will be no worse than the native launch of a C / C ++ program