使用Dijkstra算法寻找可以承载最大权重的路径
我有一个图，有 X 节点和 Y 边。加权边缘。要点是从一个节点开始，并在另一个节点（即最后一个位置）停止。现在问题来了：
想象问题。边缘是道路，边缘权重是道路上行驶的车辆的最大重量限制。我们想驾驶尽可能最大的卡车从 A 到 F。我想要从 A 到 F 的所有路径的最大允许重量。
我可以使用某种 Dijkstra 算法来解决这个问题吗？我不确定如何以我可以实现的算法的形式表达这个问题。非常感谢任何帮助。我很困惑，因为 Dijkstra 的算法只查看最短路径。
I have a graph, with X nodes and Y edges. Weighted edges. The point is to start at one node, and stop at another node which is the last location. Now here comes the problem:
Visualize the problem. The edges are roads, and the edge weights are the max weight limits for vehicles driving on the roads. We would like to drive the biggest truck possible from A to F. I want the largest maximum allowed weight for all paths from A to F.
Can I use some sort of Dijkstra's algorithm for this problem? I'm not sure how to express this problem in the form of an algorithm that I can implement. Any help is much appreciated. I'm confused because Dijkstra's algorithm just only view on shortest path.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果我理解正确的话，你想要找到一些具有最大瓶颈边的节点之间的路径。也就是说，你想要最小边尽可能大的路径。如果这是您想要解决的问题，那么可以使用 Dijkstra 算法的非常简单的修改来解决该问题。
该算法背后的想法是对 Dijkstra 算法进行一些改动。通常，在运行 Dijkstra 算法时，您会跟踪到每个节点的最短路径的长度。在修改后的 Dijkstra 算法中，您可以为每个节点存储到达该节点的任何路径上最小权重边的最大可能值。换句话说，通常在 Dijkstra 算法中，您通过找到使数量最大化的边来确定要扩展的边
其中 s 是起始节点，u 是您迄今为止探索过的某个节点，(u, v) 是一条边。在修改后的 Dijkstra 中，您会发现边缘最小化
也就是说，您考虑从源节点到您迄今为止看到的任何节点的路径上的瓶颈边缘，并考虑如果您离开那个节点并去了其他地方。这是到达目标节点的最佳瓶颈路径，您可以重复此过程。
Dijkstra 算法的这种变体也可以使用良好的优先级队列在 O(m + n log n) 时间内运行。有关更多信息，请考虑查看 这些讲座幻灯片对算法进行了简要讨论。
有趣的是，这是一个众所周知的问题，在许多算法中用作子例程。例如，解决最大流问题的早期多项式时间算法之一使用该算法作为子程序。有关详细信息，请查看这些讲义。
希望这有帮助！如果我误解了您的问题，请告诉我，以便我删除/更新此答案。
If I understand correctly, you want to find the path between some nodes that has the maximum bottleneck edge. That is, you want the path whose smallest edge is as large as possible. If this is what you want to solve, then there is a very straightforward modification of Dijkstra's algorithm that can be used to solve the problem.
The idea behind the algorithm is to run Dijkstra's algorithm with a twist. Normally, when running Dijkstra's algorithm, you keep track of the length of the shortest path to each node. In the modified Dijkstra's algorithm, you instead store, for each node, the maximum possible value of a minimum-weight edge on any path that reaches the node. In other words, normally in Dijkstra's algorithm you determine which edge to expand by finding the edge that maximizes the quantity
Where s is the start node, u is some node you've explored so far, and (u, v) is an edge. In the modified Dijkstra's, you instead find the edge minimizing
That is, you consider the bottleneck edge on the path from the source node to any node you've seen so far and consider what bottleneck path would be formed if you left that node and went some place else. This is the best bottleneck path to the target node, and you can repeat this process.
This variant of Dijkstra's algorithm also runs in O(m + n log n) time using a good priority queue. For more information, consider looking into these lecture slides that have a brief discussion of the algorithm.
Interestingly, this is a well-known problem that's used as a subroutine in many algorithms. For example, one of the early polynomial-time algorithms for solving the maximum flow problem uses this algorithm as a subroutine. For details about how, check out these lecture notes.
Hope this helps! And if I've misinterpreted your question, please let me know so I can delete/update this answer.
没有 Dijkstra，就没有流量问题。这要容易得多：只需使用您最喜欢的图形搜索（BFS 或 DFS）。
而不是计算和跟踪与到达图中某个节点相关的成本，只需计算允许使用该路径的最大卡车的“大小”（路径中所有边的权重的最小值）。当多个搜索路径在一个节点中相遇时，丢弃具有较低“卡车重量限制”的路径。
No Dijkstra, no flow problem. It's a lot easier: Just use your favorite graph search (BFS or DFS).
Instead of computing & tracking the cost associated with reaching a certain node in the graph, just compute the 'size' of the biggest truck that is allowed to use this path (the minimum of weights of all edges in the path). When multiple search paths meet in a node throw away the path that has the lower 'truck weight limit'.
这是一种简单有效的方法：
令
MAX为图中的最大边权重。二分搜索0 <= k <= MAX，这样您就可以仅使用权重为> 的边从。您可以使用广度优先搜索来看看这是否可行（不要采取如果重量太小则边缘）。A到F;= k这给出了
O((X + Y) log V)算法，其中V是权重的范围。Here is an easy and efficient way:
Let
MAXbe the maximum edge weight in the graph. Binary search0 <= k <= MAXsuch that you can get fromAtoFusing only edges with weights>= k. You can use a breadth first search to see if this is possible (don't take an edge if its weight is too small).This gives an
O((X + Y) log V)algorithm, whereVis the range of your weights.类似 Dijkstra 的算法需要的是最优子结构以及一种快速计算具有已知目标值的路径的单边扩展的目标值的方法。这里，最优子结构意味着如果有一条从顶点 x 到不同顶点 y 的最优路径，那么从 x 到倒数第二个顶点的子路径就是最优的。
（IVlad，我只能通过随机化得到 O(X + Y)。）
What a Dijkstra-like algorithm requires is optimal substructure and a way quickly to compute the objective value for a one-edge extension of a path with a known objective value. Here, optimal substructure means that if you have an optimal path from a vertex x to a different vertex y, then the subpath from x to the second-to-last vertex is optimal.
(IVlad, I only can get O(X + Y) with randomization.)