CODEWITHSUNDEEP
javascriptarraysrecursion
Kyle Boyer
Kyle Boyer

Reputation: 31

Trying to find shortest route with dictionary?

I'm currently working on creating a findPath() function. Hopefully the code below clears up any questions. I'm working in Javascript. Basically, the findPath() function takes the parameters from,to, and optionally stack. I have been able to make my function work, however I want it to get the shortest path possible. Here is my current code:

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

My issue is that when I attempt to create the aSt array of all possible routes, I get incorrect answers.

The correct answer for findPath("Isri","Harith") should be ['Isri','Eully','Harith']. However, I am getting ["Isri", "Valera", "Lisim", "Eully"]. What am I missing? What is going wrong here?

Upvotes: 0

Views: 77

Answers (1)

Kyle Boyer
Kyle Boyer

Reputation: 31

The issue is Javascript passes arrays by reference instead of by value. Simply changing the recursive call to use stack.slice(0) instead of stack creates a 'shadow' copy of the array.

Upvotes: 1

Related Questions