低內存最短路徑算法

Question

我有一個全局唯一路徑表，它可以被認爲是一個有向無權重圖。每個節點代表正在被控制的物理硬件或系統中的唯一位置。該表包含爲每個節點執行以下操作：

1. 一個唯一的路徑ID（INT）
2. 類型成分（炭 - 'A' 或 'L'）的
3. 字符串包含逗號分隔的列表該節點連接到的路徑ID（char []）

我需要創建一個給定起點和終點的函數，找到兩個節點之間的最短路徑。通常這是一個非常簡單的問題，但這是我遇到的問題。我的內存/資源數量非常有限，所以我不能使用任何動態內存分配（即隊列/鏈接列表）。如果它不是遞歸的話，它也會很好（但如果它非常小，它不會像表/圖本身那樣大，目前它有26個節點，其中8個永遠不會被命中。在最壞的情況下，總共會有大約40個節點）。

我開始把東西放在一起，但它並不總是找到最短的路徑。僞代碼如下：

bool shortestPath(int start, int end) 
    if start == end 
    if pathTable[start].nodeType == 'A' 
     Turn on part 
    end if 
    return true 
    else 
    mark the current node 
    bool val 
    for each node in connectedNodes 
     if node is not marked 
     val = shortestPath(node.PathID, end) 
     end if 
    end for 

    if val == true 
     if pathTable[start].nodeType == 'A' 
     turn on part 
     end if 
     return true 
    end if 
    end if 

    return false 

end function 

任何人有任何想法如何解決這段代碼，或知道我可以用來使其工作的其他東西？

-----------------編輯-----------------

以Aasmund的建議下，我看着實施廣度優先搜索。下面我有一些C＃代碼，我使用我在網上找到的一些僞代碼快速地扔在一起。

僞代碼在網上找到：

輸入：一個圖G和G的根v

我使用此代碼寫

procedure BFS(G,v): 
     create a queue Q 
     enqueue v onto Q 
     mark v 
     while Q is not empty: 
      t ← Q.dequeue() 
      if t is what we are looking for: 
       return t 
      for all edges e in G.adjacentEdges(t) do 
       u ← G.adjacentVertex(t,e) 
       if u is not marked: 
        mark u 
        enqueue u onto Q 
     return none 

C＃代碼：

 public static bool newCheckPath(int source, int dest) 
     { 
      Queue<PathRecord> Q = new Queue<PathRecord>(); 
      Q.Enqueue(pathTable[source]); 
      pathTable[source].markVisited(); 

      while (Q.Count != 0) 
      { 
       PathRecord t = Q.Dequeue(); 
       if (t.pathID == pathTable[dest].pathID) 
       { 
        return true; 
       } 
       else 
       { 
        string connectedPaths = pathTable[t.pathID].connectedPathID; 
        for (int x = 0; x < connectedPaths.Length && connectedPaths != "00"; x = x + 3) 
        { 
         int nextNode = Convert.ToInt32(connectedPaths.Substring(x, 2)); 

         PathRecord u = pathTable[nextNode]; 
         if (!u.wasVisited()) 
         { 
          u.markVisited(); 
          Q.Enqueue(u); 
         } 

        } 
       } 
      } 

      return false; 
     } 

此代碼運行不過，它只會告訴我路徑是否存在。這對我來說並不適合。理想情況下，我想要做的是在塊「if（t.pathID == pathTable [dest] .pathID）」我想有一個列表或一種方法來查看我必須通過哪些節點來獲取來源和目的地，以便我可以在那裏處理這些節點，而不是返回一個列表在其他地方處理。任何想法如何我可以做出這種改變？

Answer 1

最有效的解決方案，如果你願意使用靜態存儲器分配（或自動，正如我好像記得++術語是C），是聲明一個固定大小int陣列（的大小41，如果你完全確定節點數不會超過40）。通過使用兩個索引來指示隊列的開始和結束，可以將此陣列用作環形緩衝區，它可以充當廣度優先搜索中的隊列。

或者：由於節點數量非常少，Bellman-Ford可能足夠快。該算法實現簡單，不使用遞歸，並且所需的額外內存僅爲每個節點的距離（int，或者甚至是byte）以及每個節點的前導ID（int）。運行時間爲O(VE)，或者O(V^3)，其中V是節點數量，E是邊數。