我目前正在创建findPath()函数。希望下面的代码可以解决所有问题。我正在使用Javascript。基本上,findPath()函数从,到和可选地获取参数。我已经能够使我的函数正常工作,但是我希望它能获得最短的路径。这是我当前的代码:
function findPath(from, to, stack){
if(!stack) stack = [from];
var opts = getTravelOptions(from);
var aSt = [];
for(var i = 0; i < opts.length; ++i){
if(stack.indexOf(opts[i]) >= 0) continue; //No Circles
stack.push(opts[i]);
if(to == opts[i]){
return stack; //Shortest possible
}else{
var news = findPath(opts[i],to,stack);
if(news.length > 0){
aSt.push(news);
//return news;
}
}
stack.pop();
}
var shortest = [];
for(var i2 = 0; i2 < aSt.length; i2++){
if(shortest.length == 0) shortest = aSt[i2];
if(shortest.length > aSt[i2].length) shortest = aSt[i2];
}
return shortest;
}
function getTravelOptions(from){
var map = {
'Sanfew': ['Lisim','Rynir Mines'],
'Lisim': ['Sanfew','Rynir Mines','Valera'],
'Valera': ['Endarx','Isri', 'Lisim'],
'Endarx': ['Rile','Valera'],
'Rile': ['Endarx'],
'Isri': ['Valera','Eully'],
'Eully': ['Isri','Harith'],
'Harith': ['Eully', 'Port Senyn'],
'Port Senyn': ['Harith'],
'Rynir Mines': ['Sanfew','Lisim','Harith']
};
if(!from) return Object.keys(map);
return map[from];
}
我的问题是,当我尝试创建所有可能路线的aSt数组时,得到的答案不正确。
findPath(“ Isri”,“ Harith”)的正确答案应该是['Isri','Eully','Harith']。但是,我得到了[“ Isri”,“ Valera”,“ Lisim”,“ Eully”]。我想念什么?这是怎么了?
最佳答案
问题是Javascript按引用而不是按值传递数组。只需将递归调用更改为使用stack.slice(0)而不是stack即可创建数组的“影子”副本。