我有一个加权图。我想找到从节点 S 到节点 E 的最佳路径，以便该路径内的最大单边权重尽可能小。
例如：
S -> E (w=40)
S -> A (w=30)
A -> E (w=20)
对于此图，djikstra 将计算成本为 40 的最短路径为 S->E。 相反，我想要的是 S->A->E（成本最大值（30， 20） = 30）。
是否可以以这种方式修改 dijkstra？或者是否有任何已知的算法可以实现这一点？
解决此问题的方法是更改与优先级队列/堆存储距离（比较值）的方式，但除此之外，结构将保持与Dijkstra的相似。您将把到目前为止的最大权重存储在构造路径中，而不是总距离中。这样，在您的优先级队列中，您将首先按最小队列的顺序排列。
所以在你给出的例子中，它会以 S -> A 开头，因为它的 w 为 30，而另一个是 40。在第二次执行中，它将变为 w = 20，A -> E，因为 Math.max（20， 30） <40，因此它将存储在优先级队列/堆中之前。
一旦你到达目的地，那么这条路将保证是最少的。希望这是有道理的！
您可以使用贪婪算法变体：
1）删除所有边缘，并首先使用最小值对边缘进行排序。
2）按从最小到最大的顺序向图形添加边，直到有从源节点到目标节点的路径。该路径就是您正在寻找的路径。