在有向加權圖中找到給定節點的n個最接近節點的最快方法

Question

現在我在整個圖上執行Dijkstra算法，並根據距離原始節點的總距離形成最小堆節點。然後我從堆中刪除前n個元素。

這讓我感到非常低效。假設我需要找到10個最接近的節點，並且我的圖有超過100000個節點。然後在整個圖表上執行Dijkstra's似乎浪費時間。但問題是，我不能確定任何其他方式，我可以找到前10個最接近的節點，而無需計算出圖中每個節點的最短路徑。

有沒有更好的方法？

Answer 1

Dijkstra通過迭代地添加距離源最近距離的節點來工作。這是我們確信距離的節點，永遠不會有更短的路徑。所以如果我們想要找到最近的10個節點，我們可以在添加10個節點到我們的閉集後簡單地終止搜索。