Linear Array with nodes randomly linked to other nodes in array, shortest path.

Question

INFO: I have an Array of 100 nodes, [ 0 .. 99 ]. Each node can have an arbitrary number of linked nodes:

eg1, 0 links to 5, 10, 15, 20. eg2, 1 links to 30, 40, 50. eg3, etc..

All 100 nodes have at least one linked node, nodes do not know who links to them.

QUESTION: How can I find the shortest link-path if provided with START and END.

eg. START=5, END=80, Link Path (example) : [5]->10->24->36->[80]?

I'm using Pascal and/or PHP, but understanding how is what I'm looking for [code helps too].

Answer 1

Plenty of reading/algorithms: Shortest path problem. You effectively just have every edge ("link", as you called it) with an equal weight.

Answer 2

Is this a tree/graph or a forest? If it is a forest, the path may not be defined always. In case this is a tree/graph, try using Breadth-First-Search.

Think of it this way: say, you are out on a stealth mission to find cute chicks in your neighbourhood. You start at your own house and mark it as the START. You'd next go to knock on your closest neighbours, right? So, we'll do just that -- push all nodes connected to the start in a queue. Now, repeat the neighbour search for all the nodes in this queue. And keep doing this till you get your girl, err, the END.

Answer 3

Do a Breadth First Traversal starting with the Start node and quit as soon as you find the end node.

Answer 4

Does this have cycles? i.e. is it a DAG?

If there aren't cycles:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {   
       //If this is the node you are looking for...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the end node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       List<Node> bestPath = null;

       foreach(Node child in startNode.Children)
       {             
          //get the shortest path from this child
          List<Node> childPath = GetShortestPath(child, endNode);
          if (childPath != null &&
             ( bestPath == null || childPath.Count < bestPath.Count))
          { 
              bestPath = childPath;
          }
       }

       bestPath.Insert(0, startNode);
       return bestPath;
    }

[Edit: Added an example for cycles] If there can be cycles:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {
        List<Node> nodesToExclude = new List<Node>();
        return GetShortestPath(startNode, endNOde, nodesToExclude);
   }

   List<Node> GetShortestPath(Node startNode, Node endNode, List<Node> nodesToExclude)
   {   
       nodesToExclude.Add(startNode);

       List<Node> bestPath = null;

       //If this is end node...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the child node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       foreach(Node child in startNode.Children)
       {
          if (!nodesToExclude.Contains(child))
          {
              //get the shortest path from this child
              List<Node> childPath = GetShortestPath(child, endNode);
              if (childPath != null &&
                 ( bestPath == null || childPath.Count < bestPath.Count))
              { 
                  bestPath = childPath;
              }
          }
       }

       nodesToExclude.Remove(startNode);
       bestPath.Insert(0, child);

       return bestPath;
    }

Answer 5

Two structures: a set and a list.

In the set, you store nodes you have already visited. This prevents you from following cycles.

The list is of objects containing: (1) a node, and (2) a pointer back to the node that found it.

Starting at the start node, add it to the set, add it to the list with a null back reference, and then add all the nodes it can reach to the list with back references to the index 0 in the list (the start node).

Then for each element in the list thereafter, up until you reach the end, do the following:

1. if it is in the set already skip it (you have already visited it) and move to the next item in the list.
2. otherwise, add it to the set, and add all nodes it can reach to the list with back references to the index you are 'looking at' to the end of the list. Then go to the next index in the list and repeat.

If at any point you reach the end node (optimally as you are adding it to the list - as opposed to visiting it in the list), track back through the back references to the start node and invert the path.

Example:

Given nodes 0 through 3, where
node0 --> node1
node0 --> node2
node1 --> node2
node2 --> node3
and node0 is START and node3 is END

SET = {}
LIST = []

Step 1 - add START:

SET = {node0}
LIST = [[node0, null]]

Step 2 - at index 0 of the list - add reachable nodes:

SET = {node0, node1, node2}
LIST = [[node0, null], [node1, 0], [node2, 0]]

Step 3 - at index 1 of the LIST - add reachable nodes:

node2 is already in the SET. skip adding reachable nodes to LIST.
SET = {node0, node1, node2}
LIST = [[node0, null], [node1, 0], [node2, 0]]

Step 4 - at index 2 of the LIST - add reachable nodes:

SET = {node0, node1, node2, node3}
LIST = [[node0, null], [node1, 0], [node2, 0], [node3, 2]]

Step 5 - reached END, now backtrack:

The END node (node3) inserted in the LIST has a back reference to index 2 in the list, which is node2. This has a back reference to index 0 in the list, which is node0 (START). Invert this and you get a shortest path of node0 --> node2 --> node3.