递归深度优先搜索 python 即 returns 加权总计

Question

我正在尝试在 python 中编写深度优先搜索函数。我在计算最短路径的总权重时遇到了问题 return。这是我目前所拥有的..

def dfs(road,start,end,dist_so_far,path=[]):
    path = path + [start]
    if start == end:
        path.append(path)
        del path[-1]
        print(path)
    for node, weight in roads[start]:
        if node not in path:
            dfs(roads, node, end, dist_so_far, path)
    return #return total weight

我现在迷路了，对我需要做什么有什么想法吗？输入看起来像：

road = {'f': [('d', 2.0), ('g', 7.0)], 
        'b': [('a', 5.0), ('d', 6.0)], 
        'c': [('a', 8.0), ('d', 2.0)], 
        'e': [('d', 12.0), ('g', 3.0)], 
        'g': [('e', 3.0), ('f', 7.0)], 
        'a': [('b', 5.0), ('c', 8.0)], 
        'd': [('b', 6.0), ('c', 2.0), ('e', 12.0), ('f', 2.0)]}

print(dfs(road, 'a', 'b', 0.0))

我需要 return 总最短距离的功能。我对 python 还是比较陌生，我已经知道的可能是完全错误的。

编辑我想我明白了，我有点做错了..

def dfs(place, dist_so_far, roads, distances):
    if (place not in distances) or (distances[place] > dist_so_far):
        distances[place] = dist_so_far
        for combo in roads[place]:
            to_city, dist = combo
            dfs(to_city, dist_so_far+dist, roads, distances)

distances = { }
start_place = 'a'
dfs(start_place, 0.0, roads, distances )

if destination in distances :
    print("Distance from {} to {} is {}".format(start_place,destination, distances[destination]))

希望这对以后的其他人有所帮助。

Answer 1

DFS 不是 return 加权图中的最短路径，而且对于简单的无向图并不总是给出最佳答案，在这种情况下您需要使用 BFS。想象下图：

1
| \
2--3

在这个图中有一个循环，如果你使用 DFS 找到从 1 到 3 的最短路径，你会得到长度为 2 的 1-2-3 而我们可以直接从 1 到 3，但是如果你使用 BFS，你会得到正确的结果。

回到您的问题，在加权图表中，您可以根据需要或拥有的图表类型使用 Dijkstra or Bellman–Ford or Floyed。无论如何，如果你想使用 DFS 从 a->b 中找到一条路径，你可以使用全局变量来存储距离并在找到第一条路径后完成算法，如下所示：

res, found = 0, False
def dfs(roads,start,end,dist_so_far,path=[]):
    global res, found
    if found: return

    path = path + [start]
    if start == end:
        path.append(path)
        del path[-1]
        print(path)
        res = dist_so_far
        found = True
        return

    for node, weight in roads[start]:
        if node not in path:
            dfs(roads, node, end, dist_so_far+weight, path)

递归深度优先搜索 python 即 returns 加权总计

Recursive depth first search python that returns weighted total

python

recursion

depth-first-search