Направленный граф: Как найти самый длинный путь от узла A до N, учитывая код ff: - PullRequest
Новая
       12

Направленный граф: Как найти самый длинный путь от узла A до N, учитывая код ff:

1 голос
/ 19 февраля 2020

Я рассмотрел использование DFS для отслеживания вершины для каждого имеющегося ребра, чтобы найти самый длинный путь , но проблема в том, что он дает только L входные данные для это и край, соответствующий этому. Я хочу найти самый длинный путь, пройденный этими вершинами, в виде неубывающей по алфавиту строки, и если строка играет бесконечно, она выводит бесконечное число. Вот мой начальный рабочий код: 

from collections import defaultdict

def DFS(G,v,seen=None, path=None):
    if seen is None: seen = []
    if path is None: path = [v]

    seen.append(v)

    paths =[]
    for i in G[v]:
        if i not in seen:
            i_path = path + [i]
            paths.append(tuple(i_path))
            paths.extend(DFS(G, i, seen[:], i_path))

    return paths

t = int(input())
i,j = 1,0
graph = defaultdict(list)
while i < t:
    n, a = [int(i) for i in input().split()]
    while j < a:
        n1,n2,l = input().split()
        graph[l].append(n1)
        graph[l].append(n2)
        j+= 1
    print(graph)
    print(DFS(graph, 'A'))
    i+=1

Я хочу знать, где я сделал что-то не так или, может быть, я пропустил что-то важное, поскольку данный вывод для примера ввода: 

    INPUT:
        1 // test case
        5 7 // n, a
        2 3 B
        3 1 E
        1 2 A
        1 2 R
        2 4 D
        3 5 E
        4 3 D
        Expected : ADDER
        ACTUAL: D, D
...