Low Memory Shortest Path Algorithm

Question

I have a global unique path table which can be thought of as a directed un-weighted graph. Each node represents either a piece of physical hardware which is being controlled, or a unique location in the system. The table contains the following for each node:

1. A unique path ID (int)
2. Type of component (char - 'A' or 'L')
3. String which contains a comma separated list of path ID's which that node is connected to (char[])

I need to create a function which given a starting and ending node, finds the shortest path between the two nodes. Normally this is a pretty simple problem, but here is the issue I am having. I have a very limited amount of memory/resources, so I cannot use any dynamic memory allocation (ie a queue/linked list). It would also be nice if it wasn't recursive (but it wouldn't be too big of an issue if it was as the table/graph itself if really small. Currently it has 26 nodes, 8 of which will never be hit. At worst case there would be about 40 nodes total).

I started putting something together, but it doesn't always find the shortest path. The pseudo code is below:

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

Anyone have any ideas how to either fix this code, or know something else that I could use to make it work?

----------------- EDIT -----------------

Taking Aasmund's advice, I looked into implementing a Breadth First Search. Below I have some c# code which I quickly threw together using some pseudo code I found online.

pseudo code found online:

Input: A graph G and a root v of 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# code which I wrote using this code:

        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;
        }

This code runs just fine, however, it only tells me if a path exists. That doesn't really work for me. Ideally what I would like to do is in the block "if (t.pathID == pathTable[dest].pathID)" I would like to have either a list or a way to see what nodes I had to pass through to get from the source and destination, such that I can process those nodes there, rather than returning a list to process elsewhere. Any ideas on how i could make that change?

Answer 1

The most effective solution, if you're willing to use static memory allocation (or automatic, as I seem to recall that the C++ term is), is to declare a fixed-size int array (of size 41, if you're absolutely certain that the number of nodes will never exceed 40). By using two indices to indicate the start and end of the queue, you can use this array as a ring buffer, which can act as the queue in a breadth-first search.

Alternatively: Since the number of nodes is so small, Bellman-Ford may be fast enough. The algorithm is simple to implement, does not use recursion, and the required extra memory is only a distance (int, or even byte in your case) and a predecessor id (int) per node. The running time is O(VE), alternatively O(V^3), where V is the number of nodes and E is the number of edges.