Store possible travel paths from a list of addresses

Question

I have a list of addresses that we can call A-Z. I have used the Google Maps api to geocode these and then find the travel times between each of them to get a 26x26 matrix. I want to come up with a function that takes the address list, the matrix, target node ( which I will call @), and a time limit and returns a list of all possible travel paths that can be achieved from A to @ to any number of different, non-repeating destinations, and back to A before the time limit is reached.

I am thinking that a recursive function might be the best way to do this but I have only learned about them in theory and don't know if it would work.

My thoughts so far are something like this:

var duration = 0;
var path = [];

function getPath(addList, matrix, targetNode, currentNode, timeLimit){
    if(duration+matrix[matrix.indexOf(currentNode), matrix.indexOf(A)]>=timeLimit{
        path[path.length-1] = A;
        // (1) add path to the list of possible paths
    }
    else{
        var tempList = addList;
        tempList.splice(tempList.indexOf(currentNode), 1);
        for(int i = 0; i < tempList.length; i++){
            // (2) increase duration by matrix[matrix.indexOf(currentNode), matrix.indexOf(tempList[i])];
            getPath(tempList, matrix, targetNode, tempList[i], timeLimit);
        }
    }
}

I think that it would work if I could figure out:

(1) How should I store the path (A,@,...,A) as I go into the recursiveness? I cant use a single variable because each function would change it. I was thinking about using something like an xml file as a tree but that seems over the top.

(2) In a similar question, how would I continue increasing duration for each possible path?

On a final note, this would only give me the longest paths from A to @ to other nodes and back to A. I would want to include shorter paths as options as well. For example if my path is {A, @, B, C, D, A} then I would also want to include the following paths {A, @, A}, {A, @, B, A}, and {A, @, B, C, A}. The recursiveness would stop early if I stopped there though so I think that should be handled as a follow up for once the getPath function is totally resolved.

Any pointers, thoughts, help, or comments would be greatly appreciated! Thanks in advance!

Update: I just thought of using a JSON object to handle my issues. It could look something like:

var jsonPaths = [
    {
        index: 1,
        path: [A,@,A],
        duration: 187
    },
    { .... },
    { .... }
];

and I could push to it and reference it on each function call.

Answer 1

You can do this by creating a array of all paths to the target with a distance less than the maximum allowable distance minus distance of the shortest path to the target.

I would do this in two steps:

First, go through and compute the shortest path from every node to the target. Save each shortest path, along with its distance, on the node.

With all of the shortest paths computed, you can then start creating a array of possible partial paths, and a array of possible paths. To be a possible partial path, the total distance of the path plus the distance of the shortest path from the last node in the path to the target is less than the maximum path length. Possible paths are paths from a to @ that are less than the maximum path length.

You can iterate through your array of possible partial paths, at each step removing the first possible partial path and for all nodes you can travel to from the current node, check if adding that node to your current path would be a possible partial path. If so, add it to your possible partial path array . 'Nodes you can travel to' would mean nodes that you haven't already visited that are connected to your current node.

Right now, it looks like you have all the nodes connected to all of the other nodes. This could be problematic, since it gives you a maximum of 4.0329146e+26 (a.k.a 26!) possible paths from a to @. Generally, for these types of problems, you limit nodes to only be connectable to nearby nodes to avoid that much of a scaling problem, but you will still potentially be generating huge numbers of paths. ALL possible paths is potentially a large number.

I would recommend against recursion since you're generating a list of lots of things. Just create an array of possibilities and keep removing things from it/adding things to it until it's empty.

EDIT: Since all of your nodes are connected to all of the other node, from any possible potential path, you can create a path by adding the target node. This simplifies things as far as finding paths is concerned.

To find possible paths, consider that any possible path is another possible path plus one node. If you know that ABC is a possible path, you can check ABCD, ABCE, ABCF, and so on, as well as adding ABC@ to an array of half-paths.

Likewise, if ABD is not a possible path, you don't need to consider anything else starting with that path. To come up with all paths from A to @, you can start with the array [A].

Your function would look something like this:

var partialPaths = [A],
    nodes = [/*this contains all of your nodes*/],
    paths = [],
    maxDistance = totalDistance - distance([A@]), 
      //max distance of any path between A and @
    currentPath;

while(partialPaths.length > 0){
    currentPath = partialPaths.pop();

    paths.push(currentPath.concat([@]); //Adds the current path plus @

    nodes.forEach(function(node){
        if(distance(currentPath + node + @) < maxDistance &&
          (node not in current path){
            partialPaths.push(currentPath + node);
        }
    });
}

After this, you will have an array of all paths from A to @. Simply combine each path with all paths of length less that the total length minus the maximum length to get all of the round-trip paths.