使用高程查找最短路徑的圖算法

Question

考慮網格（X乘以Y）。網格中的每個點都有一個Z值。現在，在這個網格中有一個指定的檢查點。考慮網格有一個評分D.這個值D意味着你可以從任何一個檢查點到達另一個檢查點，只需要穿過一條具有最大值D的路徑。路徑的長度取決於最大高程差兩條連續的節點在該路徑中。例如，考慮海拔的網格：

1 1 1 1 1 
2 1 3 1 2                
1 2 3 1 2                

如果我走這條路：（X手段的推移，O表示不交叉的）：

X X X O O 
O O X O O 
O O X X X 

這條道路的值是2 ，因爲最高高度差異出現在你從1到3的部分。

問題是這樣的：找到允許從任何檢查點到另一個檢查點的D的最小值，這意味着D將是最大值從一個檢查點到另一個檢查點的路徑長度。

例如，如果d是2，這意味着我可以通過具有的2

，這是什麼的高效算法的最大值我一切的道路檢查站到達另一個？

Answer 1

這非常像Dijkstra的算法。從一個節點開始，探索距離越來越遠的所有節點。從設置S開始，作爲任何節點，只是第一個節點，並用距離無窮大標記其餘節點。考慮從S引出的未探索邊緣，如果相鄰未探索節點的高度差小於其標籤，則標記相鄰未探索節點。將所有最小距離的相鄰節點添加到S並重復。運行時間應該只是O(E)。

Answer 2

它看起來像你要求所有對最短路徑解決方案之一的這些網格。維基百科建議（http://en.m.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths）Floyd-Warshall（O（v^3））或約翰遜算法（O（VE + V^2 log V））將是一個不錯的選擇。由於邊的數量小於4 * V，約翰遜的算法將漸近更快。