9

您能否推荐任何实现 k-shortest 算法的 java 库 -> 寻找替代方法，而不是有向多重图中唯一最短的方法？

我只发现了 JGraphT 但实际上存在错误（我提交了）但我想修复它需要很多时间，还有其他可用的实现吗？除了 JGraphT，我只发现了小型单人项目：/

或者很难修改 Disjktra 最短路径算法以显示替代路径？

谢谢

4

3 回答 3

5

2个可能的选项：

选项 1。class KshortestPath来自MascOpt 包的 Java 实现 k 最短路径是一个不错的选择。

选项 2。您也可以从code.google.com尝试这个 这似乎是一个人的努力，但好在算法是共享的：日元排名 - 详细信息在这里。（http://www.ohloh .net/p/k-最短路径）

注意：在给定图中找到所有节点对之间的最短路径是一个不同的问题。请参阅有关Dijkstra 与 Floyd-Warshall 的这个 SO 问题。

另请注意，k-shortest paths对于丰富的图，往往是（Dijkstra）最短路径的轻微变化 - 最短路径上的顶点之间的替代路径，成本略高。

我知道 OP 要求 Java 实现，但如果人们可以选择并且 R 是一个选项，那么来自 CRAN 的kBestShortestPaths 包也是一个非常好的选择。

希望有帮助。

于 2012-10-08T03:40:48.180 回答
2

找到 k 最短路径是相关的，但与替代路径的问题并不完全相同。好的替代路径更复杂。阅读其他类似方法的概述：

  • k-最短路径
  • 帕累托最优
  • 高原法
  • 处罚方式

高原方法在这里有点说明。

如果您可以阅读德语，那么这个讲座很好：

  • 例如关于时间或距离的优化 => 问题：缺少有趣的替代方案
  • 不同的路径=>同样的问题
  • k-最短路径 => 问题：真正的替代方案可能不在前 1000 条路径下

第 5 页

所以直觉告诉我们：另一种选择应该有几乎相同的距离或时间。但应该有很大不同。所以第一个想法：找到一条最小化长度和相似性的路径。问题：可能存在局部弯路。

第 6 页

我们引入第三个标准：局部最优性：每个短子路径都需要是最短路径。

于 2012-10-08T20:23:42.167 回答
0

之前也有过类似的请求，不过是在 StackOverflow 上寻找所有的路径。 使用 DFS 查找图中的所有路径

希望这会有所帮助，它得到了回答，但不是确切的解决方案，而是更多的指南

于 2012-10-07T23:44:58.400 回答