1樓：flyingfish
如果是4000點， 幾萬邊這種極小圖，隨便floyd 都沒有問題。 如果是現實工作中遇到的千萬級別以上的點， 億級別邊的大圖， 可能需要重新定義計算最短路徑的價值了。 dijkstra 甚至都不需要。
考慮是乙個關係圖，三度以上的關係強度衰退嚴重，甚至距離大於3的點都不會有物理意義的。
2樓：
不知道你的圖有多大規模。
單源最短路徑的話，如果是稀疏圖可以考慮spfa（時間複雜度km）;如果是稠密圖可以考慮dijkstra（時間複雜度 n lg n）
多源最短路徑的話，可以用floyd。
另外，如果單機跑不了的話，這幾種演算法應該都有分布式實現
3樓：
求兩點間最短距離，可以有兩種演算法，一種是完全資訊法求出兩點間所有的路徑，從而能得到最短路徑。這裡建議你另外一種方法，不完全資訊法。
首先我假設你這個是無方向的路徑，從而你的輸入資料總是兩點間的連線首先你建立乙個資料結構，以儲存所有兩點間距離為1的資料，簡單來說，就建立乙個2維陣列好了
其次開始計算，演算法就是，從兩點間距離為1開始，尋找有沒有距離為1的，有的話，必然最短，從而無需計算所有路徑，之後每次+1，直到路徑數，大於你這個輸入檔案的行數，既大於總圖存在路徑數，這說明兩點間無路徑。
之後只是遞迴的問題了。
如何設計出精巧的資料結構？
雲悠水澈 這個問題，並不是一篇文章或一本書就能說清楚的，需要對特定問題深入的分析和大量的練習，建議多看一些成熟的協議，這些協議中的資料結構基本都很精巧，總結吸收裡面面對問題的設計思想和技巧。核心是 簡練 清楚明白。比如 iCalendar RFC 5545中怎樣準確標識乙個事務，怎樣處理乙個事務的迴...
有沒有三維的資料結構？
Ivony 我覺得這個問題下面的答案都跑偏了，事實上單連通鏈本來就是樹的一種，而陣列和單鏈表只是單連通鏈的儲存方式而已。所以根本就不存在什麼一維二維，空間維度是幾何上的定義，和圖一毛錢關係沒有。如果說陣列和單鏈表是一維的，那麼雜湊表是幾維的？能表示這種資料結構的空間維度下限這本來就不是乙個良好的定義...
學習資料結構有什麼好的教程？
資料結構和數學很類似都是比較抽象的，而往往實際問題都是非常複雜的，所以要先掌握最基本最抽象最特殊的規律。學習資料結構首先要掌握一門計算機語言，起碼要知道語法，能利用它完成一些基本程式，就像首先要掌握數學最基本的加減乘除，定理之類的規則。其次要知道資料結構和演算法是分不開的，學習資料結構的同時也需要一...