dijkstra - 有兴趣通过dijkstra算法在opl cplex中找到k个最短路径

Question

我有兴趣通过 dijkstra 算法找到从源节点到目标节点的 k 最短路径。我已经在 dvar boolean 的帮助下解决了同样的问题，以清除链接的布尔变量，如果为路径选择链接，则该变量可以取值为 1，否则为 0，但问题是该变量计算每个流的最短路径，即很费时间。现在我有兴趣摆脱流量守恒约束并使用某种类型的算法来生成列方法，这种方法可以立即解决问题，而不是计算每个变量的路径。我期待着您的回音

标签： dijkstracplex

Answer 1

如果您关心性能，那么使用通用整数规划求解器来解决这个问题可能不是一个好主意。正如你在这里看到的例子，有专门的算法可以有效地解决 k 最短路径问题。如果您想坚持使用 OPL，那么您可以使用 OPLScript 实现这些算法。