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

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".