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

Question

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

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

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

我的输入当前格式化为数组的形式，其中包含每个顶点i的邻居。因此，例如，graph[i]会为您提供顶点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
};

Answer 1

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

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

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;
}