Самая быстрая реализация алгоритма Дейкстры на javascript?

Дан взвешенный граф. Необходимо решить 2 задачи: найти из начальной точки длины путей до всех точек и также получить самый короткий (дешевый, оптимальный и т.п.) путь их одной точки в другую.

Логично напрашивается алгоритм Дейкстры.

НО!

Нужно, чтобы реализация работала быстро.
Для оценки: для 160 вершин и 350 рёбер выполнение за 3 миллисекунды - это медленно.

Я пытался найти реализации этого алгоритма на JavaScript в интернете. Однако либо они были слишком медленные
как например эта
или эта

Либо некорректно работали, т.е. зацикливались, хотя входные данные были корректны
как здесь

Также прикрепляю сюда пример со ~160 вершинами и ~350 ребрами, чтобы не надо было самому придумывать такой пример, чтобы измерить время

Ссылка на пример такого графа

Если можно как-то оптимизировать те реализации, ссылки на которые я прикрепил выше, и от этих оптимизаций они станут быстро работать, буду тоже очень признателен!
  • Вопрос задан
  • 4238 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

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

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
vabka
@vabka
Токсичный шарпист
Вариант 1:
Можно реализовать самостоятельно на js, но не использовать те фичи, которые снижают производительность.
Вариант 2:
Реализовать алгоритм на Rust и скомпилировать код под wasm.
Например есть такая либа: https://crates.io/crates/pathfinding, которую можно заиспользовать для этого
Ответ написан
Комментировать
profesor08
@profesor08 Куратор тега JavaScript
А почему Javascript? В плане времени, 3-4мс, это ничто для интерпретируемого языка (запускал код в консоли браузера из первой ссылки). Там есть странные моменты, которые можно поправить, например вот этот `if (String(child) === String(startNode))`, или сделать поменьше операций с массивами, или заранее выделить им фиксированный размер, чтоб избежать пушей и динамического выделения памяти. Если понимаешь алгоритм, то можешь пробежаться по коду и поискать моменты, где можно отбросить ненужные итерации.
Ответ написан
Комментировать
gbg
@gbg
Любые ответы на любые вопросы
Написать на С/С++ и откомпилировать при помощи wasm. С большой долей вероятности, скорость будет не хуже нативного запуска программы на С/C++
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы