Алгоритм кратчайшего пути с малым объемом памяти

У меня есть глобальная таблица уникальных путей, которую можно рассматривать как ориентированный невзвешенный граф. Каждый узел представляет собой либо часть физического оборудования, которым управляют, либо уникальное местоположение в системе. Таблица содержит следующее для каждого узла:

1. Уникальный идентификатор пути (int)
2. Тип компонента (символ — «A» или «L»)
3. Строка, содержащая список разделенных запятыми идентификаторов путей, к которым этот узел подключен (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

У кого-нибудь есть идеи, как исправить этот код или узнать что-то еще, что я мог бы использовать, чтобы он работал?

—————— РЕДАКТИРОВАТЬ ——————

Прислушавшись к совету Аасмунда, я занялся поиском по ширине. Ниже у меня есть некоторый код на C #, который я быстро скомбинировал, используя псевдокод, который я нашел в Интернете.

псевдокод, найденный онлайн:

Вход: граф G и корень v из G

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)», я хотел бы иметь список или способ увидеть, через какие узлы мне нужно было пройти, чтобы получить от источник и назначение, так что я могу обрабатывать эти узлы там, а не возвращать список для обработки в другом месте. Любые идеи о том, как я мог бы сделать это изменение?