CareerCup

Do DFS with backtracking.

Here is C# code that does the DFS using variable "visited" to keep track of previous nodes. Return value is a List of Lists, each of which contains a valid/non-cyclical route from point A to point B. Method is instance method of origination node, taking in destination node.

public List<List<TreeNode>> GetPathToNode(TreeNode destination, List<TreeNode> visited)
    {
        List<TreeNode> currentPath = new List<TreeNode>(visited) { this };

        if (this == destination)
        {
            return new List<List<TreeNode>>() { currentPath };
        }

        List<List<TreeNode>> retVal = null;
        if (ChildrenNodes != null)
        {
            foreach (TreeNode child in ChildrenNodes)
            {
                if (!currentPath.Contains(child))
                {
                    List<List<TreeNode>> childPaths = child.GetPathToNode(destination, currentPath);
                    if (childPaths != null)
                    {
                        if (retVal == null)
                        {
                            retVal = new List<List<TreeNode>>();
                        }
                        retVal.AddRange(childPaths);
                    }
                }
            }
        }
        return retVal;
    }

My solution was:
1. Use Dijkstra's algorithm to find the shortest route and store that route in a map
2. For each route found, recursively remove one link in that route from the graph, and find the next shortest route and add that to the map.

With the dataset provided, this implementation works well. However, finding "all possible routes" in a graph is a bad idea, as it becomes very computationally expensive as the number of nodes and interconnectivity increase.

But now that I think about it, DFS with backtracking may have been conceptually simpler. Though I'm not sure it would have been faster.