[Vuejs]-Performance issue with Vue.js Dijkstra algorithm

by

0👍

✅

Although you seem to suggest that your algorithm works, but too slow, it actually has at least one blocking error:

  • for (let node in toChecknext): this will iterate the indexes of the array, not the values. Yet you treat those values as nodes, which will lead to undesired behaviour. Change to:

    for (let node of toChecknext)

There are other, non-breaking issues as well:

  • if (grid[ny][nx].prev !== []) will always be true, because a newly created array can never be the same object as an already existing object. I gues you first tried with === [], then found it was always false, and then just toggled it. Instead initialise prev as null and just check whether prev is a truthy value. Also just reference node instead of grid[ny][nx], which really is the same object (see more about that in another bullet point further down this list):

    this.prev = null; // in Node constructor
/* ... */
if (node.prev)

  • toChecknext is never cleared. It should, otherwise the algorithm will be doing unnecessary work. Whenever you have copied the contents of toChecknext to this.toCheck, you should empty toChecknext so that you will not be verifying nodes that are already visited. So after the copy, add:

    toChecknext.length = 0;

  • There is no provision for the case where there is no path. The algorithm will get into an infinite loop. On the condition you did the previous correction, also add this block before the else:

    } else if (toChecknext.length == 0) {
    this.output = [];
    return []; // No solution!

  • The path pathnodes lacks the end node. So initialise it with:

    let pathnodes = [currentNode];

  • The path pathnodexy actually is reversed, as it lists coordinates from the end to the beginning. So do this:

    this.output = pathnodexy.reverse();

  • In the case the start node is the end node, you return the path, but in all other cases you do not return it, but set a property. This is inconsistent. So in the else case do this:

    this.output = [start];

    and outside of the if..else block do:

    return this.output;

  • It is overkill to do things like this.grid[node.y][node.x].id, which really is node.id. You have this happening at several places in your code. Another example is currentNode.x !== startNode.x || currentNode.y !== startNode.y, which can be just currentNode != startNode. There are other cases, which I will not list all…

  • It is of no use to pass this.grid to findNeighbours and then have findNeighbours return it. Any mutation you did on that grid argument will be directly on this.grid. grid is a reference to the same as this.grid. So just remove that parameter, and have the function work with this.grid instead of grid, and just return the neighbour list.

  • Don’t use try { ... } catch { null }, as you risk to miss out on errors you did not expect.

There is much more to improve in this code, but with these adjustments it should run in a reasonable time.

Leave a comment