k-shortest（替代）路径算法，java实现
你能推荐任何实现k-shortest算法的java库 – >搜索替代方法，而不是定向多图中唯一最短的方法吗？
我发现只有JGraphT，但实际上有bug（我提交了）但是我需要花很多时间修复它，是否有其他可用的实现？ 除了JGraphT，我发现只有小型单人项目：/
或者很难修改Disjktra最短路径alg以显示替代路径？
谢谢
2个可能的选择：
选项1. MascOpt包中的class KshortestPath是k- shortest路径的Java实现的一个很好的选择。
选项2.你也可以从code.google.com尝试这个。这似乎是一个人的努力，但好的是该算法是共享的：Yen的排名 – 详细信息在这里。（ http：//www.ohloh .net / p / k-shortest-paths ）
注意 ：查找给定图形中所有节点对之间的最短路径是另一个问题。 在Dijkstra对阵Floyd-Warshall看到这个问题。
还要注意，富图的k-shortest paths往往是（Dijkstra）最短路径的微小变化 – 最短路径上的顶点之间的替代路径，成本稍高。
我知道OP要求Java实现，但如果人们有选择而R是一个选项，那么CRAN的kBestShortestPaths 包也是一个非常好的选择。
希望有所帮助。
找到k最短路径是相关的，但不是与替代路径完全相同的问题。 良好的替代路径更复杂。 阅读其他类似方法的概述：
- k-Shortest Paths
- 帕累托最优
- 高原法
- 惩罚方法
高原方法在这里有点说明。
如果您有可能阅读德语，那么这个讲座很棒 ：
- 例如关于时间或距离的优化=>问题：缺少有趣的替代方案
- dijunct paths =>同样的问题
- k-shortest paths =>问题：真正的替代方案可能不在前1000条路径之下
第5页
所以直觉告诉我们：替代方案应该具有几乎相同的距离或时间。 但应该是显着不同的。 所以第一个想法：找到一个缩小长度和相似性的路径。 问题：可能有当地的弯路。
第6页
我们引入第三个标准： 局部最优 ：每个短子路径都需要是最短路径。
之前有类似的请求，但在StackOverflow上查找所有路径。 使用DFS查找图形中的所有路径
希望这有所帮助，它得到了回答，但没有得到确切的解决方案，而是更多的指南