python - pythonでグラフ中の最高得点パスを見つける機能

Question

有向グラフで最高スコアを見つける関数を作成しようとしています。開始ノードがありますが、同じノードを 2 回通過することはできません。再帰を使用して、1 つの終了ノードに到達するまで値の合計を取得しようとしました。次に、関数を開始ノードにコールバックし、別のオプションを最後まで試します。等々。

私の問題は、複数のパスを持つノードに戻ると、このノードのスコア値が、通過できるすべてのパスの合計になることです。そして、特定の 1 つのパスの合計のみが必要です。

これまでの私のコードは次のとおりです。

caminho = list()
def maxscore(start, parentals, score):
    global caminho
    parentals += start + '|'

    if len(graph[start]) > 0:
        for i in graph[start]:
            if i not in parentals.split('|'):
                value = graph[start][i]
                if value:
                    score += value

                func = maxscore(i, parentals, score)

            else:
                continue

        if func[0] > score:
            score = func[0]
            caminho = parentals.split('|')

        return score, caminho

    else:
        return score, start

graph = {
    'a': {'b': 2, 'c': 4},
    'b': {'d': 5},
    'c': {'a': 1, 'e': 3},
    'd': {'f': 4},
    'e': {'b': 2, 'f': 3, 'g': 2},
    'f': {},
    'g': {}
}

print(maxscore('a', '', 0))

最終的にパス（caminho）で最高のスコアのみを返すようにするにはどうすればよいでしょうか。

うまく説明できなかったらごめんなさい。ご不明な点がございましたら、お気軽にお問い合わせください。