时间戳

首页 > 解决方案 > 使用 BFS (javascript) 查找最短路径未加权图

javascript - 使用 BFS (javascript) 查找最短路径未加权图

问题描述

我正在尝试应用 BFS 来查找图中最短路径的长度，但并没有得到正确的结果。

我尝试通过访问图中的每个节点来找到最短路径；然后标记访问过的那些，并继续记录路径的长度。我希望返回的是一个包含最短路径的数组，但我认为我在这个过程中做错了什么。

我认为这与我如何索引我的数组和记录我的距离有关。

我的输入目前以数组的形式格式化，其中包含每个顶点的邻居i。因此，例如，graph[i]会给你一个 vertex 的邻居数组i。

关于如何解决我的问题的任何想法都会非常有帮助。谢谢！

var shortestPathLength = function(graph) {
    let distances = []
    let pq = []
    distances[0] = 0 
    let mygraph = {}

    for (var i = 0; i<graph.length; i++) {
        distances[i] = -1
        mygraph[i] = graph[i]
    }


    pq.push(mygraph[0])

    while(pq.length > 0) {
        let min_node = pq.shift()
        for(var i = 0; i<min_node.length; i++) {
            candidate = distances[i] + 1
            if(distances[min_node[i]]== -1) {
                distances[min_node[i]] = distances[i] + 1
                 pq.push(graph[min_node[i]])
            }
            else if (candidate < distances[min_node[i]]) {
                distances[min_node[i]] = distances[i] + 1
            }

        }
    }

    function getSum(total, num) {
        return total + num;
    }

    console.log(distances)
    return distances.length

};

标签： javascriptalgorithmbreadth-first-search

解决方案

你的问题是candidate = distances[i] + 1。是 内边的i索引min_node，这一点都不有趣。您正在寻找的是当前到min_node. 您需要将距离指定为min_node对象本身的属性，或者您需要将graph节点的 id（in 中的索引）存储在队列中，而不是对象本身。

我做了一些其他的简化，但你的代码中唯一的问题是距离查找。

function shortestPathLength = function(graph) {
    const distances = Array(graph.length).fill(-1);
    distances[0] = 0; // start node
    const queue = [0];

    while (queue.length > 0) {
        const node_index = queue.shift();
//                 ^^^^^
        const edges = graph[node_index]; // get the node itself
        const candidate = distances[node_index] + 1; // outside of the loop
//      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        for (const target in edges) {
            if (distances[target] == -1) {
                distances[target] = candidate;
                queue.push(target); // not graph[target]
//                         ^^^^^^
            }
        }
    }
    return distances;
}

推荐阅读