# Collect distances from 1 point to all others in a graph

Problem:
I have a weighted graph. I want to get distance from definite point to all other points in the graph.(and then get path to them)
I used modified dijkstra algorithm

So, here is code:

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,
prev: null,
};
}
root = cache[a];
root.distance = 0;
queue = [root];

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

return cache;
}


Graph format is:

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


Performance:
In my PC this algorithm works with graph of ~160 vertices and ~350 edges about 0.03-0.06ms. But I need faster!

You can measure performance on your PC here

Question: How to make this code (function get_path()) faster? Is it possible on JavaScript? If I should change the format of graph to make algorithm faster it's not a problem.

Or I exhausted possibilities of JavaScript?

• Your code is optimal as a general purpose solution so for further optimization you will need to target known structural regularities. EG if the set of nodes A must pass through C to get to nodes not in A. You can then cache all shortest paths from C to any node in A. Any path from B (B is not in set A) to B1 (B1 is in set A) need only find shortest path to C, the path from C to B1 will be cached by index of B1. Without knowing what the graph represents or how and how often it is constructed there is no way of knowing if such optimizations will pay off Feb 5, 2021 at 15:09

Interesting question;

Naming

• The names are on the whole terrible, it really blocks the reading flow, the only good 1 letter variable is i
• Further evidence of the bad naming is that I only realized that n, w, and max are never used because of jshint.com
• JavaScript follows lowerCamelCase so get_path -> getPath
• In fact, even getPath would be a bad name, because you are not getting a path, getPaths could be better (you are getting more than 1 ), but getDistances or even getDistancesFromNode seems best

Declarations

• You are mixing var and let in your code, I would stick to let and const

• You are not declaring res at all (now it's a global) because this

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


should be

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


Performance

This is already quite impressive, the only thing I noticed is that you process child nodes even if their child count is one (meaning really zero, since that 1 node must be the parent).

I assume the while loops are meant to be the fastest approach, however it seems that the fastest approach is now the most readable approach.

If you were allowed to just use/modify graph instead of cache it would be faster, of course the code reviewer would have told you that's not clean ;)

All in all, if I had to maintain this, then I would rewrite with proper variable names but otherwise this is perfectly maintainable.

function getDistancesFromNode(graph, origin) {

let cache, i, j, queue, node, links, root,
link, nextNode, distance, nodeCount = graph.length;

cache = Array(nodeCount);
i = nodeCount;
while (--i >= 0) {
node = graph[i];
cache[node.id] = {
id: node.id,
distance: Infinity,
prev: null,
};
}
root = cache[origin];
root.distance = 0;
queue = [root];

i = 0;
while (i < queue.length) {
node = queue[i];
while (--j >= 0) {
distance = node.distance + nextNode.weight;
if (distance < nextNode.distance && nextNode.links.length > 1) {
nextNode.prev = node;
nextNode.distance = d;
queue.push(nextNode);
}
}
i++;
}
return cache
};

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,
prev: null,
};
}
root = cache[a];
root.distance = 0;
queue = [root];

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

return cache
};

var times = [], newTimes = [];

for (let i=0; i < 1000; i++) {
var s_t = performance.now();
res = get_path(graph, 157);
times.push(performance.now() - s_t);
}

for (let i=0; i < 1000; i++) {
var s_t = performance.now();
res = getDistancesFromNode(graph, 157);
newTimes.push(performance.now() - s_t);
}

function average(nums) {
return nums.reduce((a, b) => (a + b)) / nums.length;
}

console.log(average(times), 'ms')
console.log(average(newTimes), 'ms')

• what's wrong with variable name? And can you tell me more details about optimization to make it faster? I should use graph instead of cache? I am afriad, that it will broke the algorithm. Feb 4, 2021 at 23:43
• I rewrote with better variable names, I hope you can appreciate the difference in readability. Feb 5, 2021 at 15:08