javascript - 使用Dijkstra算法寻找能够承载最大权重的路径

Question

我有一个图，有 X 个节点和 Y 个边。加权边缘。重点是从一个节点开始，并在最后一个位置的另一个节点停止。现在问题来了:

将问题可视化。边缘是道路，边缘权重是在道路上行驶的车辆的最大重量限制。我们想驾驶最大的卡车从 A 到 F。我想要从 A 到 F 的所有路径的最大允许重量。

我可以使用某种 Dijkstra 算法来解决这个问题吗？我不确定如何以我可以实现的算法的形式来表达这个问题。任何帮助深表感谢。我很困惑，因为 Dijkstra 算法只考虑最短路径。

Answer 1

如果我没理解错的话，你想找到一些具有最大瓶颈边的节点之间的路径。也就是说，你想要最小边尽可能大的路径。如果这是您要解决的问题，那么可以使用对 Dijkstra 算法进行非常直接的修改来解决该问题。

该算法背后的想法是运行 Dijkstra 算法并加以改变。通常，在运行 Dijkstra 算法时，您会跟踪到每个节点的最短路径的长度。在修改后的 Dijkstra 算法中，您改为为每个节点存储到达该节点的任何路径上最小权重边的最大可能值。换句话说，通常在 Dijkstra 算法中，您通过找到使数量最大化的边来确定要扩展的边

d(s, u) + l(u, v)

其中 s 是起始节点，u 是您目前探索过的某个节点，(u, v) 是边。在修改后的 Dijkstra 中，您反而会发现边缘最小化

min(bottleneck(s, u), l(u, v))

也就是说，您考虑从源节点到您目前看到的任何节点的路径上的瓶颈边缘，并考虑如果您离开该节点并前往其他地方会形成什么瓶颈路径。这是到达目标节点的最佳瓶颈路径，您可以重复此过程。

Dijkstra 算法的这种变体使用良好的优先级队列也可以在 O(m + n log n) 时间内运行。有关更多信息，请考虑查看 these lecture slides对算法进行了简要讨论。

有趣的是，这是一个众所周知的问题，在许多算法中用作子例程。例如，解决最大流问题的早期多项式时间算法之一使用该算法作为子程序。有关操作的详细信息，请查看 these lecture notes .

希望对您有所帮助!如果我误解了您的问题，请告诉我，以便我删除/更新此答案。