图最小权重路径
Graph minimum weight path
我有一个加权图。
我想找到从节点 S 到节点 E 的最佳路径，以便该路径内的最大单边权重尽可能小。
例如：
S -> E (w=40)
S -> A (w=30)
A -> E (w=20)
对于此图，djikstra 会计算出最短路径为 S->E，成本为 40。我想要的是 S->A->E（成本为 max(30, 20) = 30） .
是否可以这样修改dijkstra？
或者是否有任何已知算法可以完成此操作？
解决这个问题的方法是改变存储优先级队列/堆的距离（比较值）的方式，否则结构将与 Dijkstra 的相似。您可以将到目前为止的最大重量存储在构建的路径中，而不是总距离中。这样，在您的优先级队列中，您将首先为最小的队列排序。
所以在你给出的例子中，它会从 S -> A 开始，因为它的 w 为 30，而另一个是 40。在第二次执行中，它会转到 w = 20，A - > E 因为 Math.max(20, 30) < 40，所以它会先存储在优先级队列/堆中。
一旦到达目的地，那这条路就一定是最短的。希望这是有道理的！
您可以使用贪心算法变体：
1)移除所有边，边以最小值排序。
2) 按照从最小到最大的顺序向图中添加边，直到存在从源节点到目标节点的路径。该路径就是您要查找的路径。
我有一个加权图。 我想找到从节点 S 到节点 E 的最佳路径，以便该路径内的最大单边权重尽可能小。
例如：
S -> E (w=40)
S -> A (w=30)
A -> E (w=20)
对于此图，djikstra 会计算出最短路径为 S->E，成本为 40。我想要的是 S->A->E（成本为 max(30, 20) = 30） .
是否可以这样修改dijkstra？ 或者是否有任何已知算法可以完成此操作？
解决这个问题的方法是改变存储优先级队列/堆的距离（比较值）的方式，否则结构将与 Dijkstra 的相似。您可以将到目前为止的最大重量存储在构建的路径中，而不是总距离中。这样，在您的优先级队列中，您将首先为最小的队列排序。
所以在你给出的例子中，它会从 S -> A 开始，因为它的 w 为 30，而另一个是 40。在第二次执行中，它会转到 w = 20，A - > E 因为 Math.max(20, 30) < 40，所以它会先存储在优先级队列/堆中。
一旦到达目的地，那这条路就一定是最短的。希望这是有道理的！
您可以使用贪心算法变体：
1)移除所有边，边以最小值排序。
2) 按照从最小到最大的顺序向图中添加边，直到存在从源节点到目标节点的路径。该路径就是您要查找的路径。