Dijkstra算法實現的最佳數據結構是什麼？ C＃

我使用C＃.NET進行編程。在實現Dijkstra算法時，通常使用優先級隊列或堆來確定下一個要訪問的節點。不幸的是，C＃本身不提供這些數據結構。我不能，也不想在數組上實現Dijkstra（這很慢）。什麼是最好的選擇？Dijkstra算法實現的最佳數據結構是什麼？ C＃

來源

2013-01-14 Patryk

爲什麼「關閉」票最短路徑算法？這是一個很好的，可回答的問題... – dasblinkenlight

當你搜索'優先隊列或堆'和C＃時，谷歌會說什麼？ –

@dasblinkenlight沒有OP沒有顯示任何努力。通過快速搜索很容易找到大量的實現。還有一個可回答的問題不適合SO。 –

從.NET 2.0開始，您可以使用SortedDictionary<K,V>來實現您的優先級隊列。它的Keys屬性返回一個有序集合。您可以提取其第一個項目以獲取代表您的「下一個最佳」邊緣的條目的關鍵字。 V需要是List<T>，其中T是您存儲在Dijkstra隊列中的元素。

來源

2013-01-14 22:16:31 dasblinkenlight

@Patryk'myDict.Keys.First（）'讓你獲得列表的關鍵;刪除它的第一個項目，如果列表爲空，則刪除該項。 – dasblinkenlight

我可以找到某處它是什麼時間複雜性？（First（）方法） – Patryk

@Patryk是的，它在[docs]（http://msdn.microsoft.com/en-us/library/f7fta44c.aspx）中提及（間接，但是）：「SortedDictionary 泛型類是一個帶有'O（log n）'檢索「的二叉搜索樹。第一項的檢索是'O（1）'，但插入是'O（log n）'。 – dasblinkenlight