我如何使用A星算法找到的第100条最短路径？
Answer 1:
找到第k个最短路径问题是NP难的 ，所以任何修改，A-明星你是什么后，会做-将在输入的规模指数。
证明：
（注：我将展示的简单路径）
假设你有，在多项式时间内运行，并返回的长度的多项式算法k最短路径让算法是A(G,k)
路径的最大数量为n! ，并通过在范围施加二进制搜索[1,n!]找到长度的最短路径n ，需要O(log(n!)) = O(nlogn)的invokations A 。
如果您发现有长度的路径n -这是哈密尔顿路径 。
通过重复该过程对于每个源和目标中的曲线图（ O(n^2)的那些），可以解决汉弥尔顿路径问题多项式，假设这样的A存在。
QED
由此我们可以得出结论，即除非P = NP （这是不太可能根据大多数CS研究员），这个问题不能得到解决多项式。
一个替代方案是使用的变化一致成本搜索而不保持visited / closed集。 你也许可以修改A *为好， 通过禁用封闭节点 ，并产生/生成一次遇到，而不是返回他们和整理解决方案，但我不能想办法证明它对于目前A *。
Answer 2:
除了这个问题是的NP难的，这是不可能的做到这一点A*或dijkstra没有大的改动。 下面是一些主要的原因：
首先，该算法保持在每一步只能到此为止的最佳路径。 请看下面的图表：
A
/ \
S C-E
\ /
B
假定距离d(S,A)=1, d(S,B)=2, d(A,C)=d(B,C)=d(C,E)=10 。
当访问c您会选择通过路径A ，但你会无处存放通过的路径B 。 所以，你必须保持这一信息。
但是，其次，你甚至不考虑每一个可能的路径，假设如下图：
S------A--E
\ /
B--C
假定距离d(S,A)=1, d(S,B)=2, d(B,C)=1, d(A,E)=3 。 您访问的订单将是{S,A,B,C,E} 所以，当访问A你甚至无法通过保存的弯路B和C ，因为你不知道它。 你得添加类似为每个未访问的邻居“通过C潜在的路径”。
第三，你必须纳入循环和小路囊的 ，因为是的，这是完全可能的，在它的循环路径最终被你100条的最短路径之一。 当然，你可能要约束这种消失，但它是一个通用的可能性。 例如，考虑图表所示：
S-A--D--E
| |
B--C
很明显，你可以轻松地开始循环这里，除非你禁止“回去”（例如禁止D->A ，如果A->D已在路径）。 其实这是没有明显的图形循环，甚至一个问题，因为在一般情况下，你可以随时两个邻居之间（路径乒乓ABABA-... ）。
而现在我可能即使忘记了一些问题。
需要注意的是这些东西大部分使它也很难制定一个通用的算法，肯定是最后一部分，因为与循环就很难限制你的可能路径号（“死循环”）。
Answer 3:
这不是一个NP硬的算法，和下面的链接是日元的算法用于在多项式时间的曲线图计算K-最短路径。 甄子丹的算法链接
Answer 4:
使用*搜索，当目的地是第k次推到队列中。 这将是第k个最短路径。
文章来源: How can I use the A star algorithm to find the first 100 shortest paths?
