algorithm - 用A*算法找出几条最短路径

Question

我正在制作一个使用 A* 算法寻找路线的路线选择应用程序。我不仅要提供一条路线，还要提供几条备选路线。例如，比最佳路线稍长的路线。

由于 A*(和许多其他)只能找到一条路线，我该如何搜索这些备选路线？我应该使用其他算法吗？

Answer 1

您可能需要研究关于 K shortest paths 的研究问题，也就是寻找两个节点之间的k条最短路径的问题。维基百科页面上描述的算法是 Dijkstra's algorithm 的概括。 .

To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path. The K Shortest path routing algorithm is a generalization of the shortest path problem. The algorithm not only finds the shortest path, but also K other paths in order of increasing cost. K is the number of shortest paths to find. The problem can be restricted to have the K shortest path without loops (loopless K shortest path) or with loop.

一些关键论文和概念:

• Finding the k shortest paths , 大卫·爱普斯坦, 1997
• A description of the problem
• Yen's algorithm :“该算法假定 Dijkstra 算法用于查找两个节点之间的最短路径，但可以使用任何最短路径算法代替它。”大概可以使用A*。可以找到各种实现的 Google 代码页 here .
• 详细Bibtex bibliography关于这个话题，由 Eppstein 编译。