algorithm - 开发线性时间算法来遍历图

Question

我正在阅读一本算法教科书来提高我的算法技能，但我完全被这个问题困住了，它一直困扰着我。我认为底层数据结构是一个图表，但我什至不知道从哪里开始解决这个问题。谁能提供一些见解？谢谢

You are given a topographical map that provides the maximum altitude along the direct road between any two neighboring cities, and two cities a and b. Come up with an a linear time algorithm that finds a route from s to t that minimizes the maximum altitude. Roads can be traversed in both directions.

Answer 1

这是一个棘手的问题。我假设本章中有一些提示可以指导您找到解决方案。

您所描述的问题是极小极大路径问题或最宽路径问题的一个实例。 http://en.wikipedia.org/wiki/Widest_path_problem

根据维基百科，有一个线性时间算法，但它非常复杂，所以我怀疑这本书是否希望您弄明白。解决这个问题比较简单的方法是找一棵最小生成树。由于最小生成树的“min cut”属性，沿着最小生成树连接a和b的路径将具有minimax属性，这意味着沿着这条路径的最大高度将是连接a到b的任何路径的最小值.

但是，没有线性时间最小生成树算法。另一方面，如果我们可以假设该图是平面的——我们可能会这样做，因为它是一张路线图——那么就有可能在线性时间内找到最小生成树。所以我认为这就是他们可能想要的。包含此问题的章节是否讨论了最小生成树和/或平面图？