algorithm - 最低成本路径，目的地未知

Question

问题
当目的地未知但遍历的边数是固定值时，如何找到成本最低的路径？这个问题或解决它的算法是否有特定的名称？

请注意，也许术语“步行”比“路径”更合适，我不确定。

解释
假设您有一个加权图，并且从顶点 V1 开始。目标是找到一条长度为 N(其中 N 是遍历的边数，可以多次穿过同一条边，可以重新访问顶点)且成本最小的路径。需要对所有可能的起始顶点重复此过程。

作为一种额外的启发式方法，考虑一个回合制游戏，其中房间由走廊相连。每条走廊都有与之相关的成本，并且您的最终分数会降低等于每个“已支付”成本的金额。穿过走廊需要 1 回合，游戏持续 10 回合。你可以呆在一个房间里(自循环)，但呆在原地也有与之相关的成本。如果您知道所有走廊的成本(以及留在每个房间的成本；即，您知道加权图)，那么进行 10 轮(或 N 轮)游戏的最佳(得分最高)路径是什么？您可以重新访问房间和走廊。

可能的方法(可能会失败)
我最初想使用 Dijkstra 算法在所有顶点对之间找到成本最低的路径，然后为每个起始顶点子集找到长度为 N 的 LCP。但是，我意识到这可能不会给出 LCP对于给定的起始顶点，长度为 N。例如，Dijkstra 的 V1 和 V2 之间的 LCP 的长度可能 < N，而 Dijkstra 的可能排除了一条不必要但成本低的边，如果包含该边，路径长度将等于 N。

Answer 1

这是一个有趣的事实，如果 A 是邻接矩阵并且您计算 A^k 使用加法和最小值代替普通矩阵乘法中通常使用的乘法和求和 , 那么 A^k[i,j] 就是从节点 i 到节点 j 恰好有 k 条边的最短路径的长度。现在的诀窍是使用重复平方，这样 A^k 只需要 log k 矩阵乘法运算。

如果除了最小长度之外还需要路径，则必须跟踪每个最小操作的结果来自何处。

为了您的目的，您需要结果矩阵每一行的最小值的位置和相应的路径。

如果图是密集的，这是一个很好的算法。如果它是稀疏的，那么对每个节点进行一次面包优先搜索到深度 k 会更快。