一個網格地圖，它可以訪問一些節點的最短路徑算法

我有一個網格地圖，我需要找到兩個節點之間的最短路徑，但該路徑必須包含一些節點。一個網格地圖，它可以訪問一些節點的最短路徑算法

我想過嘗試所有的排列，但地圖大小和必須節點的數量將是可變的，所以我想使用一個最佳算法。

的地圖將與此類似： map

-Dark brown square at Y18 is the start point 
-Light brown squares from B20 to S20 are the end point (can make just one end point if needed) 
-White squares are walls (you cannot go through them) 
-Blue squares means that the point in front of it is a must-pass (for example, the blue square at q5-q6 means must pass zone of p5-p6)

我要使用Java，我會作出這樣的映射與它們之間的連接的圖形（例如S10與S9連接， o10和s11）。

非常感謝您的幫助，如果您有任何問題，請隨時詢問。

來源

2017-05-09 Alberto Mendiolagoitia

據我瞭解，這是兩個問題的組合;您有起點，目標節點和強制中間節點。爲了確定最短路徑，您必須計算起始節點和所有中間節點之間的距離，所有中間節點對以及從每個中間節點到目的地的距離。如果只涉及非負邊緣權重，則可以用Dijkstra的算法完成。

一旦計算出所有距離，就必須計算從起始節點到目的地節點的最佳Hamiltonian path，其中使用所有中間節點。但是，由於這個問題是NP-hard，它很可能無法使用高效算法來解決;所有排列組合都可能是可行的。

來源

2017-05-09 08:01:49 Codor

首先，感謝回答如此之快！那麼，我需要得到每一對節點之間的所有距離？（0，a）和（0，b），（0，a）和（0，c）...（20，y）和（20，z）和它們之間的距離與他們一起使用哈密爾頓路徑？ –

@AlbertoMendiolagoitia：你「需要獲得每對」S之間的所有距離，其中S是[必須通過節點集合]與2元素集合{starting_node ，ending_node}。根據必須傳遞節點的數量與節點總數的比較，獲取_all_對之間的距離可能或不可能是最快的方法，但即使是，那麼你可以丟棄不是都在S中的節點之間的距離。 –

漸近地說，這可能不會起作用，因爲您仍然需要解決Hamilton路徑，但是要計算每個節點之間的距離，您可以使用Floyd-Warshall來代替以加速一點點。

來源

2017-05-09 21:27:21

一個網格地圖，它可以訪問一些節點的最短路徑算法

回答

相關問題