algorithm - 使用动态规划在加权图中找到最小的最大权重

Question

我正在寻找一种算法，该算法可以找到从两个顶点说s到t的路径，如果存在路径，则该图中恰好具有k边。

如果找到多条路径，则优先选择具有单个边的最小最大权重的路径。（不是总重量）。

例如：说 K = 5

路径 1： s - a - b - c - d - t 权重为 1 - 1 - 1 - 10 - 1

路径 1 的最大权重为 10

路径 2： s - x - y - z - w - t 权重为 7 - 9 - 8 - 6 - 7

路径 2 的最大权重是 9，所以这是首选。

我该如何解决这个问题？

Answer 1

You could use a modified version of the Floyd-Warshal algorithm that only iterates for K steps and forces the path lengths (by removing the min part)