A* find the second shortest path

Question

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.

Does path with same distance qualifies as *second shortest*? — J0HN, May 13 '14 at 09:46

score 3 · Answer 1 · answered May 13 '14 at 09:37

3

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

answered May 13 '14 at 09:37

phil_20686

4,000
21
38

To find the n-th shortest path for a constant n, the problem clearly takes polynomial time. All you did was show that the solution you presented takes time exponential in n - that's not how you prove / show NP-hardness. – Bernhard Barker May 13 '14 at 14:56
1

The n^th shortest path takes n^n using this method, which is exponential growth in n. Obviously this is not a proof, but I believe this problem is known to be NP-Hard in general. Show =/= proves. – phil_20686 May 13 '14 at 15:10
Incidentally, I believe a solution to the kth fastest route is equivalent to a solution of the Hamiltonian path problem, which is known to be NP-HARD. See http://stackoverflow.com/questions/14088898/how-can-i-use-the-a-star-algorithm-to-find-the-first-100-shortest-paths?rq=1 – phil_20686 May 13 '14 at 15:20

score 0 · Answer 2 · answered May 13 '14 at 09:59

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.

score 0 · Answer 3 · answered May 14 '14 at 01:58

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.

A* find the second shortest path

3 Answers3