我有一个全局唯一路径表，可以将其视为有向非加权图。每个节点要么代表一个被控制的物理硬件，要么代表系统中的一个唯一位置。该表包含每个节点的以下内容：
- 唯一的路径 ID (int)
- 组件类型（char - 'A' 或 'L'）
- 字符串，其中包含该节点连接到的路径 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)”块中，我想要一个列表或一种方法来查看我必须通过哪些节点才能从中获取源和目的地，这样我就可以在那里处理这些节点，而不是返回一个列表以在其他地方处理。关于我如何做出改变的任何想法？