C # алгоритм поиска всех путей между двумя вершинами

Недавно была поставлена задача реализовать в C#ориентированный граф с весами.

Я нахожусь на 3/4 пути туда, но я должен использовать тестовые данные и возвращать ответы, основанные на этих данных.

У меня есть график работы, и я могу добавить затраты между 2 узлами, а также вернуть все пути между 2 узлами, используя поиск по глубине.

Что меня озадачивает, так это то, что один из вопросов заключается в следующем: найти количество маршрутов от узла "С" до "С" со стоимостью менее 30.

Приведенный пример ответа

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"

Я могу получить

CDC,
CEBC,
CDEBC

Используя поиск по глубине, но я понятия не имею, откуда взялись остальные 4 или почему вы рассматриваете маршрут, который вы уже приземляетесь в узле назначения и продолжаете двигаться дальше.

Я использую неправильный алгоритм? Вот что я пытаюсь сделать:

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