[問題] 陣列無法宣告太大?(最短路徑演算法)

[hfuman ()]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 

.net C++  2010

額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 
no
參考網站:http://www.csie.ntnu.edu.tw/~u91029/Path2.html
問題(Question)：

目前嘗試使用最短路徑演算法於程式碼中

但是這演算法有個缺點,就是假設路徑點有300個,就要宣告陣列[300][300]

在路徑點少的case可以正常運作

如今有個case,其中路徑點約有32,000個,所以要宣告陣列[32000][32000]

結果就出現"陣列的總大小不能超過 0x7fffffff 位元組"的錯誤訊息

不知道各位大大有無其他建議,或是哪個演算法轉成程式語言後可以支援到這麼多筆資料??

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.110.234
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1400752883.A.60F.html
→ hfuman:還是net 2010 可以將陣列開到最大?
→ chunhsiang:用動態產生的看看吧
推 lsc36:如果已知邊的數量不會太多的話改用adjacency list存圖
→ haoboo:用new去產生動態陣列
→ hfuman:有測試過動態分配了~結果一樣不能~會卡住
→ AntaresStar:相鄰矩陣沒辦法算太大的圖  一定得換
→ AntaresStar:否則就是要找sparse matrix的函式庫來用
推 Littlechozy:推樓上，存一大堆0非常浪費空間，我是自己寫啦
推 blackwindy:我算了一下大概是1G個元素 還好吧
→ blackwindy:64bit下應該要得到這麼大塊沒問題
→ brighton16:第一感會想要用adjacency list做,但如果要配合演算法
→ brighton16:用sparse matrix應該可以更動較少的程式碼完成
→ ACMANIAC:哪個最短路徑演算法一定要用 matrix?
推 Killercat:0X7fffffff在以前是VC的debug limit 最新版不知道還有沒
→ Killercat:有這限制，試試看把他改用release build看看
→ Killercat:另外像這種演算法一定要找出lazy evalution method
→ Killercat:用mapping的方式 只new需要的node在對應到一張map上
→ Killercat:一口氣就急吼吼的不管有用沒用先alloc再說 就有這問題
→ Killercat:另外你是用什麼type去要[x][y]?
→ Killercat:喔對上面有人提到了 sparse matrix XD
→ hfuman:不好意思~我沒甚麼接觸到sparse matrix~我會去了解內容
→ hfuman:我是取得檔案筆數後~再去用迴圈來動態的new 二維陣列
我是將各點到各點的最點距離都先算好 存在陣列中
※ 編輯: hfuman (59.102.152.119), 05/24/2014 20:49:30
推 Killercat:boost有提供sparse matrix，可以用用看
推 suhorng:用 adjacent list 呀...
→ suhorng:對每個點用個 vector<int> 存誰與他相鄰
→ suhorng:直接用矩陣的話就算是 O(E log V) 的演算法也會變 O(V^2)