二部分加权图DFS/Greedy BFS中最便宜的路径

Question

我有一个二部分加权图（更确切地说是一个赋值问题），我想找到最便宜的路径/选择。你知道我将如何实现DFS或贪婪的BFS来实现这条道路吗？

我有一个像这样的图表示为绝热列表（或者我认为最好）和DFS算法

adjlist = {"A": ["W", "X"],
           "B": ["W", "X", "Y", "Z"],
           "C": ["Y", "Z"],
           "D": ["W", "X", "Y", "Z"],
           "W": ["A", "B", "D"],
           "X": ["A", "B", "D"],
           "Y": ["B", "C", "D"],
           "Z": ["B", "C", "D"] }
def dfser(graph, root):
    visited =[]
    stack = [root, ]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend([x for x in graph[node] if x not in visited])
    return visited

这可能是我想要的吗？结果一定是这样的：AWBXCYDZ或金额最便宜的东西。

或者我可以从根获取所有可能的遍历吗？这个DFS只给了我一个，但我想要所有可能的交易

Answer 1

BFS或DFS不是为最短路径搜索而设计的，尤其是在加权图中。

寻找最便宜的路径可以用dijkstra或A*算法来执行。Networkx为该任务提供了完整的API。

networkx模块实现了二分图和相关算法：

Dicti = {"A": {"W": 2, "X": 2},
     "B": {"W": 4, "X": 3, "Y": 2, "Z": 5},
     "C": {"Y": 2, "Z": 2},
     "D": {"W": 5, "X": 5, "Y": 4, "Z": 3},
     "W": {"A": 2, "B": 4, "D": 5},
     "X": {"A": 2, "B": 3, "D": 5},
     "Y": {"B": 2, "C": 2, "D": 4},
     "Z": {"B": 5, "C": 2, "D": 3}
}
graph = nx.Graph()
for node, succs in Dicti.items():
    for succ, weight in succs:
        graph.add_edge(node, succ, weight=weight)
print(nx.dijkstra_path(graph, 'A', 'Z'))  # here is Dijkstra