CODEWITHSUNDEEP
algorithma-star
Gasim
Gasim

Reputation: 7961

A* find the second shortest path

I am trying to achieve 2nd, preferably nth shortest path using the A* pathfinding algorithm. I have implemented the shortest path already:

while(open.length > 0) {
    max = worldSize;
    min = -1;
    for(i in open) {
        if(open[i].f < max) {
            max = open[i].f;
            min = i;
        }
    }

    node = open.splice(min, 1)[0];
    if(node.value === nodeEnd.value) {
        path = closed[closed.push(node)-1];
        do {
            result.push({x: path.x, y:path.y});
        } while(path = path.parent);
            open = closed = astar = [];
        result.reverse();
    } else {
        neighbors = findNeighbors(node.x, node.y);
        for(i = 0; i < neighbors.length; ++i) {
            path = newNode(node, neighbors[i]);
            if(!astar[path.value]) {
                path.g = node.g + manhattanDistance(neighbors[i], node);
                path.f = path.g + manhattanDistance(neighbors[i], nodeEnd);
                open.push(path);
                astar[path.value] = true;
            }

        }
        closed.push(node);
    }   
}

What can I do? I have zero experience in this and don't even understand the algorithm to its fullest (still researching at the moment). Thank you.

Upvotes: 0

Views: 1160

Answers (3)

Semicolons and Duct Tape
Semicolons and Duct Tape

Reputation: 3136

An approximate solution is to run the A* algorithm multiple times with the following caveat:

  • After you find the current shortest path
  • mark the node that came right before the end node
  • next time you run the algorithm, don't allow that node to be used e.g. set it's path.f value to infinity or something huge. or just don't add it to the open list when it is a neighbor of your current node.
  • the newly found path will be the next shortest

A couple of notes:

  • This is approximate
  • It will not work after all the nodes connected to the end have been cycled through.
  • In terrain with a complicated set of paths and obstacles you may cut off the possible routes
  • if the next shortest path could be acheived by making a decision earlier in the path finding algorithm you won't capture it. to capture that you would have to cycle through the whole path in the manner described disallowing one node at a time and taking shortest path of all the possible computed paths - this will become a mess and get out of hand quickly as the number of nodes increase.

hope that helps.

Upvotes: 0

J0HN
J0HN

Reputation: 26921

if(node.value === nodeEnd.value) is search termination condition. It means that the algorithm found some path from start to end. The essense of A* and, specifically, properties of heuristic function (admissability and consistency) guarantees that first time you arrive at termination condition gives you a shortest path.

Moreover, admissable and consistent heuristics also guarantees that all possible paths from start to end always checked from shortest to longest

So in order to get Nth closest path you only need to allow search algorithm to continue N-1 times, e.g.

hit_count = 0
while(open.length > 0) {
    // same as before
    if(node.value === nodeEnd.value) {
          path = closed[closed.push(node)-1];
          hit_count += 1;
          if (hit_count == N - 1) {
              do {
                  result.push({x: path.x, y:path.y});
              } while(path = path.parent);
              open = closed = astar = [];
              result.reverse();
          }
    }
    else { 
         // same as before
    }
}

Please note that such an approach will yield paths of the same length as new paths, i.e. if you have two paths of exaclty same length one of them would be reported as shortest and other as second shortest, depending on details of implementation.

If you want to consider all paths with the same length "identical", so "second-shortest" actually longer than shortest, just replace hit_count += 1 to

// Don't forget to initialize last_found_path_length outside the loop to zero
if (path.length() != last_found_path_length) {
    last_found_path_length = path.length();
    hit_count += 1
}

Plase note that you haven't specified what language it is (feels like Javascript) so examples here might contain syntactic errors or refer to missing methods. But I hope the approach is clear.

Upvotes: 0

phil_20686
phil_20686

Reputation: 4080

So this problem is in general NP hard. Since you only need the second shortest path, you can do it tractably. Basically, given the shortest path, you generate a collection of graphs by taking the original graph and removing one edge from the shortest path. So if you have a shortest path of length N, on a graph G(E,N), you end up with N graphs of G(E-1,V). Now you run A* on each of these graphs, and the shortest one is your second shortest path, as is it the shortest path which is different from the original shortest path by at least one edge.

This also shows why it is NP hard in practice. If I want the third shortest path, I have to to the following procedure only removing one edge from each of the two shortest paths, and the number of such pairs grows exponentially. N->N^2->N^3 etc

Upvotes: 3

Related Questions