#javascript #algorithm #performance #math #graph
#javascript #алгоритм #Производительность #математика #График
Вопрос:
Проблема:
У меня есть взвешенный график. Я хочу получить расстояние от определенной точки до всех остальных точек графика.(а затем получить путь к ним)
Я использовал модифицированный алгоритм Дейкстры
Итак, вот код:
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?
Комментарии:
1. Если вам нужно быстрее, вы имеете в виду, что у вас есть графики, которые намного больше, или что вам нужно решить много графиков?
2. Поскольку в вашем вопросе указано, что вам нужны расстояния, вы уже можете отказаться от управления
prev
.3. если вам нужно вычислить весь кратчайший путь, рассмотрите возможность использования алгоритма Флойда-Варшалла
4. кроме того, cosndier использует networkx. Для вас готовы эти алгоритмы
5. @trincot, у меня есть график, который меняет каждый кадр. Мне нужно запустить этот алгоритм из разных точек этого графика в одном кадре. Также мне нужно, возможно, восстановить путь, что
prev
помогает мне это сделать.