c++ - 最多使用 k 个顶点的有向加权图中的最短路径

Question

我正在尝试解决具有非负权重的连通有向加权循环图中的 SSSP 问题。这里的问题是，这个问题要求使用最多 k 个顶点的 SSSP。

我尝试使用修改后的 dijkstra 算法来解决这个问题，在我的优先级队列中保留一个三元组。即(顶点权重，到该顶点的路径中的顶点数(含)，顶点索引)。我的算法防止超过 k 个顶点的节点被插入优先级队列，从而被考虑在最短路径中。

不知何故，我的算法得到了错误的答案。一个原因是，如果最初较小的加权边导致无效路径，而最初较大的加权边导致有效路径，那么我的算法(贪婪)将报告它找不到到达目的地的有效路径。

编辑:已编辑解决方案代码，因为它没有帮助。

Answer 1

我发现很难阅读你的代码 - 所以也许你已经在这样做了:给每个顶点一个最佳路径的集合(编辑:实际上每个顶点只存储每条可能路径的前一步)，为该数量的访问顶点存储最便宜的路径，一旦路径超过最大顶点数，您可以丢弃它，但您不能丢弃更昂贵的(就总边长而言)路径，直到您知道更便宜的路径最终会在可接受的顶点数内到达目标。最后你可能有不止一条完整的路径，你只需要选择边缘成本最低的而不考虑它的顶点数量(如果太多你已经丢弃它了)

(如果你为你存储的一些东西创建一个类/结构，你的代码会更容易阅读，然后你可以给成员起比 second.first 等更清晰的名字。即使你对当前的命名没问题，如果以上没有帮助，额外的清晰度可能会帮助您获得其他答案。)

编辑回答:“在我知道成本较低的路径将导致解决方案之前，我如何保留成本较高的路径？”

您的优先级队列几乎已经这样做了——并不是每个顶点 (n) 都像我最初暗示的那样存储了完整的路径，目前您只存储最好的前一个顶点 (n-1) 以用于到达顶点 n - 及其成本和顶点数。我的意思是，不是存储顶点 n-1 的一个最佳选择，而是存储多个选项，例如使用 3 个先前顶点到 A 的最佳路线是从顶点 B 开始，成本为 12，使用 4 的最佳路线是从顶点 C 开始，成本为 10。(在所有上述最佳方式中，到目前为止在搜索中找到的最佳方式)

您只需要存储给定数量的顶点的最便宜路线。如果(但仅当)它在成本或顶点数上更好，您可以保留一条路线。

在我上面的示例中，您需要保留两者，因为到该顶点的更便宜的路径使用了更多先前的顶点，因此可能导致在到达目标之前有太多的顶点 - 在那个阶段不清楚最终哪条路径是最好的。

所以你需要改变你的收藏类型，以及你的丢弃选项的规则。例如，您可以使用 std::map，其中以前的顶点计数是键，总边成本和以前的顶点 ID 存储在值中，或者使用总成本数组，其中索引是计数。