python - 使用python在图中查找最高分路径的函数

Question

我正在尝试创建一个函数来查找有向图中的最高分。我有一个起始节点，不能两次通过同一个节点。我尝试使用递归来获取值的总和，直到我到达一个末端节点。然后我会将我的函数回调到起始节点并尝试其他选项直到我点击另一个。等等。

我的问题是，当我返回到具有多条路径的节点时，该节点的得分值是它可以采用的所有路径的总和。我只想要一个特定路径的总和。

到目前为止，这是我的代码:

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)。

抱歉，如果我说得不够清楚。请随时提出任何问题。

Answer 1

您可能想按值发送分数变量，但您是通过引用发送它，因此所有可能路径的分数都会添加到它。

这是我的方法:

def maxscore(start, parentals, score):
    newParentals = parentals + start + '|'
    print newParentals, score
    scores = []
    if graph[start]:
        for nextNode in graph[start]:
            if nextNode not in newParentals.split('|'):
                scores.append(maxscore(nextNode, newParentals, score + graph[start][nextNode]))
        return sorted(scores)[-1]
    else:
        return score

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))

这是打印的内容:

a| 0
a|c| 4
a|c|e| 7
a|c|e|b| 9
a|c|e|b|d| 14
a|c|e|b|d|f| 18
a|c|e|g| 9
a|c|e|f| 10
a|b| 2
a|b|d| 7
a|b|d|f| 11
18

你可以看到它是如何检查所有可能的路径，然后选择最高分的:D