如何找到通過至少一個強制節點的兩個節點之間的最短距離？

Question

我有一個具有約5000個節點的雙向加權圖表 我有一個「重要」節點（100左右）列表。給定一個起始節點和一個結束節點，如何找到這兩個節點之間的最短距離，這兩個節點至少通過一個「重要」節點。請注意，沒有負面的邊緣。我實現了dijkstra的算法來找到給定兩個節點的最短距離。我知道如何解決這個問題的唯一方法是查看重要節點列表，找到所有重要節點從開始 - >重要節點＃1 - >結束的距離，然後取最小值。有沒有更快的方法來解決這個問題？

Answer 1

你的方法是絕對正確的，你需要的是應用Dijkstra更少的次數。 這個問題很容易通過應用Dijkstra兩次來解決。

• 應用Dijkstra算法與開始源。將數組中的距離從S中存儲。

• 再次申請Dijkstra。這次以結束作爲來源。將數組中的距離存儲到E。 由於你的圖是無向最短距離從端節點到每個其他節點是相同的最短距離從每個其他節點到端節點。 （這是訣竅）。

• 找到需要的最短距離。

  For node in importantNodes : 
      ans = min (fromS [node] + toE[node] , ans) 
  return ans