在鏈表圖實現

Question

Dijkstra算法大問題，我有一個鏈表實現我的圖中，兩個頂點和邊，並且正在成爲Dijkstra算法的問題。正如我在上一個問題中所說的，我正在轉換this code，它使用一個鄰接矩陣來處理我的圖形實現。

問題是，當我找到最小值時，我得到一個數組索引。如果圖頂點存儲在數組中，該索引將與頂點索引匹配。而對頂點的訪問將是不變的。

我沒有時間更改我的圖形實現，但我確實有一個散列表，由唯一編號索引（但不是從0開始，它就像100090000），這是我的問題有。無論何時我需要，我使用模運算符來獲得一個介於0和頂點總數之間的數字。

這對於當我需要一個數組索引從數字工作正常，但是當我需要的數量從數組索引（訪問恆定的時間所計算出的最小距離頂點），沒有這麼多。

我試圖尋找如何反模操作，如，100090000 MOD 18000 = 10000和10000 invmod 18000 = 10009萬，但無法找到一個方法來做到這一點。

我的下一個選擇是構建某種參考數組，其中，在上面的示例中，arr [10000] = 100090000.這將解決問題，但需要再次循環整個圖形。

我對當前的圖形實現有更好的/更簡單的解決方案嗎？

Answer 1

在你的陣列，而不是僅僅存儲計（或任何你存儲在那裏），存儲其中包含數以及頂點索引號的結構。