C# algorithm search for all paths between two vertices

Question

Recently given a task to implement a directed graph with weights in C#.

I am 3/4 of the way there but I have to use test data and return answers based on that data.

I have the graph working and I am able to add the costs between 2 nodes as well as return all paths between 2 nodes using a depth first search.

What is baffling me is that one of the questions are as follows: find the number of routes from node "C" to "C" with a cost of less than 30.

The sample answer given is

CDC, 
CBEC, 
CEBCDC, 
CDEBC, 
CEBCEBC, 
CEBCEBCEBC  **7 in total**
These are the input graph details 
"A to B: 5",
"B to C: 4", 
"C to D: 8", 
"D to C: 8", 
"D to E: 6",
"A to D: 5" 
"C to E: 2", 
"E to B: 3", 
"A to E: 7"

I can get

CDC,
CEBC,
CDEBC

using depth first search but I have no idea as to where the other 4 are from or why you would consider a route that you already land back at the destination node and continue on.

Am I using the wrong algorithm? Here is what I'm trying:

public void depthSearch(GraphDeclare<string> graph, LinkedList<DirectedGraphNode<string>> Visited)
    {
        string endNode = "C";
        LinkedList<DirectedGraphNode<string>> nodes = getNeighboursAdjecentNodes(graph, Visited.Last());
        //examine the adjecent nodes
        foreach (DirectedGraphNode<string> node in nodes)
        {

            Boolean contains = Visited.Any(x => x.Value == node.Value);

            if (contains == true)
            {
                // Console.WriteLine("Hello");
                // printPath(Visited);
                continue;
            }
            if (node.Value == endNode)
            {
                Visited.AddLast(node);
                printPath(Visited);
                Visited.RemoveLast();
                break;
            }
        }

        foreach (DirectedGraphNode<string> node in nodes)
        {

            Boolean contain = Visited.Any(x => x.Value == node.Value);

            if (contain == true || node.Value == endNode)
            {
                continue;
            }
            Visited.AddLast(node);
            depthSearch(graph, Visited);
            Visited.RemoveLast();
        }

    }

    private void printPath(LinkedList<DirectedGraphNode<string>> visited)
    {
        StringBuilder cb = new StringBuilder();
        foreach (DirectedGraphNode<string> node in visited)
        {
            cb.AppendLine(node.Value + " ");

        }
        Console.WriteLine(cb.ToString());
    }


    private LinkedList<DirectedGraphNode<string>> getNeighboursAdjecentNodes(GraphDeclare<string> graph, DirectedGraphNode<string> n)
    {
        LinkedList<DirectedGraphNode<string>> neighbours = new LinkedList<DirectedGraphNode<string>>();

        foreach (DirectedGraphNode<string> edge in graph.nodeSet)
        {

            if (edge.Value.Equals(n.Value))
            {
                foreach (DirectedGraphNode<string> neighbour in edge.NeighbourNodes)
                {
                    neighbours.AddLast(neighbour);
                }

            }
        }

        return neighbours;
    }

Answer 1

Steps of DFS Algorithm to get all paths between two nodes:

1. Maintain list of nodes Visited, I am doing it by using visited nodes list

2. Keep on Adding nodes in a path

3. Once end node is found in a path add that path in a collectio, in the code it is done within build path method

           public List<List<RiverNode>> FindAllPathsBetweenTwoNodes(Node startNode, Node endNode, List<string> vistedNodes, List<Node> localpaths)
                   {
                       try
                       {
                           //Mark Current Node As Visited
                           vistedNodes.Add(startNode.Name);
                           if (localpaths.Count == 0)
                           {
                               localpaths.Add(startNode);
                           }
   
                           if (startNode.Name.Equals(endNode.Name))
                           {
                               BuildPath(localpaths);
                           }
   
                           foreach (var node in startNode.GetNeighbours())
                           {
                               if (!vistedNodes.Contains(node.Name))
                               {
                                   localpaths.Add(node);
                                   FindAllPathsBetweenTwoNodes(node, endNode, vistedNodes, localpaths);
                                   localpaths.Remove(node);
                               }
                           }
                           vistedNodes.Remove(startNode.Name);
                           return allPaths;
                       }
                       catch (Exception ex)
                       {
                           throw;
                       }
                   }
   
   
   
                   // <summary>
                   /// Build Path
                   /// </summary>
                   /// <param name="localpath"></param>
                   private void BuildPath(List<RiverNode> localpath)
                   {
                       var localbuilPath = new List<RiverNode>();
                       foreach (var item in localpath)
                       {
                           localbuilPath.Add(item);
                       }
                       allPaths.Add(localbuilPath);
                   }
   

Answer 2

You can modify DFS to continue using all nodes even if they have been visited, and you should stop the algorithm when the overall distance exceeds 30. You should also update your counter for the searched paths each time you get to "C".