c++ - 低内存最短路径算法

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)” block 中，我希望有一个列表或一种方法来查看我必须通过哪些节点才能从中获取源和目的地，这样我就可以在那里处理这些节点，而不是返回一个列表在其他地方处理。关于如何做出改变有什么想法吗？

Answer 1

如果您愿意使用静态内存分配(或自动，我似乎记得C++术语是这样)，最有效的解决方案是声明一个固定大小的 int 数组(大小为 41，如果您绝对确定节点数量永远不会超过 40)。通过使用两个索引来指示队列的开始和结束，您可以将此数组用作环形缓冲区，它可以充当广度优先搜索中的队列。

或者:由于节点数量太少，Bellman-Ford可能足够快。该算法实现起来很简单，不使用递归，所需的额外内存只是一个距离(int，甚至在您的情况下是byte)和一个前驱id( int) 每个节点。运行时间为 O(VE)，或者 O(V^3)，其中 V 是节点数，E 是边数。