我有一个加权图。我想找到从节点 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？或者是否有任何已知的算法可以做到这一点？
问问题
848 次
2 回答
1
解决此问题的方法是更改存储与优先级队列/堆的距离（比较值）的方式，但除此之外，结构将保持与 Dijkstra 的相似。到目前为止，您会将最大权重存储在构造路径中，而不是总距离中。这样，在您的优先级队列中，您将首先按最小的顺序排列。
因此，在您给出的示例中，它将以 S -> A 开头，因为它的 aw 为 30，而另一个是 40。在第二次执行中，它将变为 w = 20，A -> E 因为数学。 max(20, 30) < 40，所以它会先存储在优先级队列/堆中。
一旦你到达目的地，那么这条路肯定是最少的。希望这是有道理的！
于 2016-07-13T16:20:07.663 回答
0
您可以使用贪心算法变体：
1）删除所有边缘，并首先用 min 对边缘进行排序。
2）将边添加到图中，按从最小值到最大值的顺序，直到有一条从源节点到目标节点的路径。那条路就是你要找的路。
于 2016-07-13T17:16:59.437 回答