Самая быстрая реализация алгоритма Дейкстры на javascript?
Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.
Вариант 1:
 Можно реализовать самостоятельно на js, но не использовать те фичи, которые снижают производительность.
Вариант 2:
 Реализовать алгоритм на Rust и скомпилировать код под wasm.
Например есть такая либа: https://crates.io/crates/pathfinding, которую можно заиспользовать для этого