Vue.js Dijkstra 算法的性能问题

Question

我正在写一个大学项目，我采用两种算法并比较它们的性能，主要算法是 Dijkstra 和 A*，但是我对 Vue.js、一般 JS 和算法都不是很有经验，我的第一个 Dijkstra 迭代非常慢。我正在使用 X 乘 Y 的二维网格，具有起点节点和终点节点，以及运行算法。任何大于 10x10 的网格都太慢了。

我不知所措，当运行代码执行时我没有看到任何错误，但执行速度太慢了。我不是很有经验，所以我不知道从哪里开始看，问题可能是什么。也许有经验的人可以提供帮助并告诉我我做错了什么？

    export default ({
        name: 'Home',
        data() {                                                   // global variables init
            return {
                grid: [],                                          // initializing grid array, rows and columns
                todis: "",                                         // to display
                output: [],                                        // shortest path array
                toCheck: [],                                       // checking neighboring nodes
                startx: Number(0),                                 // starting x position of algorithm
                starty: Number(0),                                 // starting y position of algorithm 
                endx: Number(0),                                   // end x position of algorithm   
                endy: Number(0),                                   // end y position of algorithm 
                sxy: [0, 0],                                       // start x, y array coordinates
                exy: [0, 0],                                       // end x, y array coordinates
                wallx: Number(0),                                  // wall x coordinate
                wally: Number(0)                                   // wall y coordinate
            };
        },
        methods: {                                                 // all needed methods
            addToGrid(adding) {                                    // create the grid 
                this.grid.push(adding)
            },
            setwall(x, y) {
                this.grid[Number(y)][Number(x)].id = 1
            },
            updates(x, y) {                                        // update start position on button press
                this.sxy = [Number(x), Number(y)]
            },
            updatee(x, y) {                                        // update end position on button press
                this.exy = [Number(x), Number(y)]
            },
            makeGrid(width, height) {                              // takes two values to make a grid
                function Node(x, y, id) {                          // 0 - unchecked; 1 - Wall; 2 - Start; 3 - End; 4 - Checked; 5 - Shortest Path
                    this.x = x                                     // initialization of values for class Node
                    this.y = y
                    this.id = id
                    this.visited = false
                    this.prev = []
                }
                if (this.grid.length === 0) {                      // Stops grid being made multiple times
                    for (let y = 0; y < height; y++) {
                        let row = []                               // Create a row, need new empty array every time we go through a row
                        for (let x = 0; x < width; x++) {          // Create nodes for the width of the grid
                            var newNode = new Node(x, y, 0)        // give values x, y, id to the node
                            row.push(newNode)                      // push a node to the row array
                        }
                        this.addToGrid(row)                        // we add row array to grid
                    }
                }
            },
            Dijkstra(start, end) {                          
                this.grid[start[1]][start[0]].id = 2               // node array coordinates (w, h we got from inputs from the front end) width height values set to id of 2, which is the start of the grid 
                this.grid[end[1]][end[0]].id = 3                   // node array coordinates (w, h) for end point, which has an id of 3
                function findNeighbours(grid, x, y) {              // scanning the neighboring nodes, takes the whole grid
                    let Neighbours = []                            // initializing values for neighbours
                    let PosNeighbours = []                         // position of new neighbours
                    let cnode = null                               // checked node 
                    grid[y][x].visited = true
                    if (grid[y][x].id === 0) {                     // if the node at y, x id is 0 (unchecked), set it to checked (for colouring)
                        grid[y][x].id = 4
                    }
                    try {                                          // we go to the right of of the node
                        cnode = grid[y][x + 1]                     // x + 1 and if the node:
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y][x + 1]) // we add set the neighbour position to that value
                            }
                        }
                    }
                    catch{
                        null
                    }
                    try {                                          // we go to the left of the node
                        cnode = grid[y][x - 1]                     // x - 1 and if the node:
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y][x - 1]) // we add set the neighbour position to that value
                            }
                        }
                    }
                    catch{
                        null
                    }
                    try {                                          // we go to the top of the node
                        cnode = grid[y + 1][x]                     // y + 1 and if the node:
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y + 1][x]) // we add set the neighbour position to that value
                            }
                        }
                    }
                    catch{
                        null
                    }
                    try {                                          // we go to the bottom of the node 
                        cnode = grid[y - 1][x]                     // y - 1 and if the node: 
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y - 1][x]) // we add set the neighbour position to that value    
                            }
                        }
                    }
                    catch{
                        null
                    }
                    for (let node of PosNeighbours) {              // for each neighboring node
                        if (typeof grid[node.y][node.x] === 'undefined') {
                            null                                   // if the node is not valid, do nothing
                        }
                        else {
                            if (node.visited === false) {          // if the node is not visited, we add the value to the neighbours array
                                Neighbours.push(node)              // we set the new x and new y value to our current node position
                                let nx = node.x
                                let ny = node.y
                                if (grid[ny][nx].prev !== []) {    // if the new grid position has no previous value 
                                    grid[ny][nx].prev = grid[y][x] // we set the previous value to the old x and y positions
                                }
                            }
                        }
                    }
                    return [Neighbours, grid]                      // ??? return an array of nodes visited and whole grid ???
                }
                if (start !== end) {                               // we start the algorithm if the start node is not the same as the end node
                    let startNode = this.grid[start[1]][start[0]]  // set the start node, the checking array, give it a start node and declare what to check next
                    this.toCheck = []           
                    this.toCheck.push(startNode)
                    let toChecknext = []
                    while (this.grid[end[1]][end[0]].visited === false) {
                        if (this.toCheck.length !== 0) {           // while we haven't visited the end node, or if we haven't checked all the nodes
                            let node = this.toCheck.shift()        // we set the node to the first value of our toCheck array
                            let fn = findNeighbours(this.grid, node.x, node.y)
                            let nodestoadd = fn[0]                 // we call the findNeighbours function and set the nodes to add to Neighbours 
                            this.grid = fn[1]                      // grid generated with grid values of the the function
                            for (let node of nodestoadd) {         // for each node in the nodestoadd array we push the node valeu to the next node to check
                                toChecknext.push(node)
                            }
                        } else {                                   // otherwise, set the next node to check to the node we are currently at
                            for (let node in toChecknext) {
                                this.toCheck.push(node)
                            }
                        }
                    }
                    let currentNode = this.grid[end[1]][end[0]]    // we set up our currentNode end, if our current node x, y are not the same 
                    let pathnodes = []
                    while (currentNode.x !== startNode.x || currentNode.y !== startNode.y) {
                        pathnodes.push(currentNode.prev)           // we create a path of the previous nodes, using a pathnodes array
                        currentNode = currentNode.prev
                    }
                    let pathnodexy = []                            
                    for (let node of pathnodes) {                  // for each node in the pathnodes array (all the nodes for our shortest path)
                        pathnodexy.push([node.x, node.y])          // we give the pathnodexy array x, y values of the nodes
                        if (this.grid[node.y][node.x].id == 4) {   // if that node has been visited with id 4, we set that to id 5, which is the id of the path
                            this.grid[node.y][node.x].id = 5
                        }
                    }
                    this.output = pathnodexy                       // we set the output value and start the algo
                } else {
                    return [start]
                }
            },

            displayGrid(grid) {                                    // we create a string method, that creates a grid with the ID values we defined
                this.todis = "<div id='block_container'>"
                for(const row of grid) {                           // for each row, and each node in that row we set the ID value of the node and generate html to create our grid
                    for (const node of row) {
                        this.todis += "<button @click.self='changewall' id='block-id-"+node.id+"'></button>"
                    }
                    this.todis += "</div><div id='block_container'>"
                }
                this.todis = this.todis+"</div>"
                return this.todis                                   // we return the constructed html
            },
            changeGrid(thisx, thisy) {
                this.grid[thisy][thisx].id = 1
            }
        },
        created: function () {
            this.makeGrid(7, 7)

        },
        updated: function () {
            // on update
        }
    });

Answer 1

虽然你的算法似乎是可行的，但太慢了，它实际上至少有一个阻塞错误：

for (let node in toChecknext)：这将迭代数组的 indexes，而不是值。然而，您将这些值视为节点，这将导致不良行为。更改为：
```
for (let node of toChecknext)
```

还有其他非破坏性问题：

if (grid[ny][nx].prev !== []) 将总是为真，因为新创建的数组永远不可能与已经存在的对象相同。我猜你首先尝试使用 === []，然后发现它总是 false，然后只是切换它。而是将 prev 初始化为 null 并检查 prev 是否为真值。也只需引用 node 而不是 grid[ny][nx]，这实际上是同一个对象（请参阅此列表下方的另一个要点中的更多信息）：
```
this.prev = null; // in Node constructor
/* ... */
if (node.prev)
```
toChecknext 永远不会被清除。它应该，否则算法将做不必要的工作。每当您将 toChecknext 的内容复制到 this.toCheck 时，您应该清空 toChecknext，这样您就不会验证已经访问过的节点。所以在复制之后，加上：
```
toChecknext.length = 0;
```
没有路径的情况没有规定。该算法将进入无限循环。在你做了前面更正的情况下，还要在 else:
之前添加这个块
```
} else if (toChecknext.length == 0) {
    this.output = [];
    return []; // No solution!
```
路径pathnodes缺少结束节点。所以初始化它：
```
let pathnodes = [currentNode];
```
路径pathnodexy实际上是相反的，因为它列出了从末尾到开头的坐标。所以这样做：
```
this.output = pathnodexy.reverse();
```
在开始节点是结束节点的情况下，你return路径，但在所有其他情况下你不return它，而是设置一个属性。这是不一致的。所以在 else 的情况下这样做：
```
this.output = [start];
```
在 if..else 块之外执行：
```
return this.output;
```
做this.grid[node.y][node.x].id这样的事情太过分了，实际上是node.id。您在代码中的多个位置都发生了这种情况。另一个例子是 currentNode.x !== startNode.x || currentNode.y !== startNode.y，它可以只是 currentNode != startNode。还有其他情况，我就不一一列举了...
把this.grid传给findNeighbours再有findNeighboursreturn是没有用的。您对 grid 参数所做的任何更改都将直接在 this.grid 上进行。 grid 是对与 this.grid 相同的引用。所以只需删除该参数，并让函数使用 this.grid 而不是 grid，并且只使用 return 邻居列表。
不要使用 try { ... } catch { null }，因为您可能会错过意想不到的错误。

此代码还有很多需要改进的地方，但通过这些调整，它应该运行在合理的时间内。

Vue.js Dijkstra 算法的性能问题

Performance issue with Vue.js Dijkstra algorithm

algorithm

performance

dijkstra

vue.js