使用动态规划查找加权图中的最小最大权重
我正在寻找一种算法，可以找到图中从两个顶点 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，因此这是首选。
我到底该如何解决这个问题呢？
I'm looking for an algorithm that finds the path from two vertices say s to t, in a graph that has exactly k edges if paths exist.
And if multiple paths were found, the one with the minimum maximum weights of a single edge is preferred. (not the overall weights).
eg: say K = 5
Path 1: s - a - b - c - d - t with weights 1 - 1 - 1 - 10 - 1
the maximum weight of path 1 is 10
Path 2: s - x - y - z - w - t with weights 7 - 9 - 8 - 6 - 7
the maximum weight of path 2 is 9, so this is preferred.
How exactly do I solve this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以使用仅迭代的 Floyd-Warshal 算法的修改版本K 步骤并强制路径长度（通过删除
min部分）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
minpart)