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

Question

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

Answer 1

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