Соберите расстояния от одной точки до всех остальных на графике

Проблема:

У меня есть взвешенный график. Я хочу получить расстояние от определенной точки до всех других точек на графике. (А затем получить путь к ним)
Я использовал модифицированный алгоритм Дейкстры

Итак, вот код:

var get_path = function(graph, a) {
// declaration
let cache, i, v, queue, node, links, root,
    j, link, c, n, d, max, w, L = graph.length;

// initialization
cache = Array(L);
i = L;
while (--i >= 0) {
    v = graph[i];
    cache[v.id] = {
        id: v.id,
        distance: Infinity,
        links: v.links,
        prev: null,
    };
}
root = cache[a];
root.distance = 0;
queue = [root];

// processing
i = 0;
while (i < queue.length) {
    node = queue[i];
    links = node.links;
    j = links.length;
    while (--j >= 0) {
        link = links[j];
        c = cache[link.id];
        d = node.distance + link.weight;
        if (d < c.distance) {
            c.prev = node;
            c.distance = d;
            queue.push(c);
        }
    }
    i++;
}

return cache;
}

Формат графика является:

graph = [
  {
    id: 1,
    links: [
      {
        id: 2,
        weight: 1,
      },
      {
        id: 3,
        weight: 1,
      },
    ],
  },
  {
    id: 2,
    links: [
      {
        id: 1,
        weight: 1,
      },
      {
        id: 4,
        weight: 2,
      }
    ]
  },
  {
    id: 3,
    links: [
      {
        id: 1,
        weight: 1,
      },
      {
        id: 4,
        weight: 3,
      }
    ]
  },
  {
    id: 4,
    links: [
      {
        id: 2,
        weight: 2,
      },
      {
        id: 1,
        weight: 1,
      },
      {
        id: 3,
        weight: 3,
      },
      {
        id: 5,
        weight: 1,
      }
    ]
  }, 
  {
    id: 5,
    links: [
      {
        id: 4,
        weight: 1,
      }
    ]
  }
]

Спектакль:

На моем ПК этот алгоритм работает с графом из ~ 160 вершин и ~ 350 ребер примерно 0,03-0,06 мс. Но мне нужно быстрее!

Вы можете измерить производительность на своем ПК Вот

Вопрос:
Как сделать этот код (функцию get_path()) Быстрее? Возможно ли это на JavaScript? Если мне нужно изменить формат графика, чтобы алгоритм работал быстрее, это не проблема.

Или я исчерпал возможности JavaScript?

Интересный вопрос;

Именование

• Имена в целом ужасные, действительно блокирует поток чтения, единственная хорошая однобуквенная переменная — это i
• Еще одним свидетельством плохого наименования является то, что я только понял, что n, w, и max никогда не используются из-за jshint.com
• JavaScript следует за lowerCamelCase, поэтому get_path -> getPath

Декларации

• Вы смешиваете var и let в вашем коде я бы придерживался let и const

• Вы не заявляете res вообще (теперь он глобальный), потому что это

  var s_t = performance.now()
  res = get_path(graph, 157)
  

  должно быть

  var s_t = performance.now(),
  res = get_path(graph, 157)
  

Спектакль

Это уже впечатляет, единственное, что я заметил, — это то, что вы обрабатываете дочерние узлы, даже если их количество дочерних узлов равно единице (что означает действительно ноль, поскольку этот 1 узел должен быть родительским).

Я предполагаю while циклы должны быть самым быстрым подходом, однако кажется, что самый быстрый подход сейчас читаемый подход.

Если бы вам разрешили просто использовать / изменять graph вместо того cache это было бы быстрее, конечно, обозреватель кода сказал бы вам, что это не чисто;)

Комментарии

Комментарии должны быть содержательными, эти комментарии достаточно очевидны.

В общем, если бы мне пришлось это поддерживать, я бы переписал с правильными именами переменных, но в остальном это прекрасно обслуживается.