algorithm - A *找到第二条最短路径

我正在尝试使用A*寻路算法实现第二条，最好是第N条最短路径。我已经实现了最短路径：

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

我能做什么我在这方面没有经验，甚至没有充分理解算法（目前仍在研究）。谢谢您。

最佳答案

所以这个问题一般是np难的。因为你只需要第二条最短的路径，所以你做起来很容易基本上，给定最短路径，通过获取原始图并从最短路径中删除一条边来生成一组图。因此，如果在图g（e，n）上有一条长度为n的最短路径，则最终得到n个图g（e-1，v）。现在对这些图中的每一个都运行一个*号，最短的一个是第二个最短的路径，最短的一个是与原来的最短路径至少有一条边不同的最短路径。
这也说明了它在实践中是NP难的原因如果我想要第三条最短路径，我必须按照以下步骤，只从两条最短路径中的每一条中删除一条边，并且这样的对的数量呈指数增长。N->N^2->N^3等

关于algorithm - A *找到第二条最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23623324/