Блог

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

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

 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?