python代码以及测试案例

好的，下面是使用分支限界法求解单源路径问题的Python代码和一个简单的测试案例：

from queue import PriorityQueue

def find_shortest_path(graph, start, end):
    # 初始化搜索树和优先队列
    queue = PriorityQueue()
    queue.put((0, [start]))  # 初始路径为[start]，代价为0
    visited = set()

    # 循环扩展节点
    while not queue.empty():
        # 取出队列中的队首节点
        (cost, path) = queue.get()
        node = path[-1]

        # 如果该节点已经被访问过，则跳过
        if node in visited:
            continue

        # 如果该节点是目标节点，则返回结果
        if node == end:
            return (cost, path)

        # 否则，将该节点标记为已访问，并扩展其所有子节点
        visited.add(node)
        for neighbor, weight in graph[node].items():
            if neighbor not in visited:
                # 计算新路径的代价
                new_cost = cost + weight
                new_path = path + [neighbor]
                # 将新路径加入优先队列中
                queue.put((new_cost, new_path))

    # 如果无法找到目标节点，则返回None
    return None

# 测试案例
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'D': 1, 'E': 3},
    'C': {'F': 4},
    'D': {'G': 6},
    'E': {'G': 4},
    'F': {'G': 3},
    'G': {}
}
start = 'A'
end = 'G'
result = find_shortest_path(graph, start, end)
print(result)  # 输出(9, ['A', 'C', 'F', 'G'])

在上面的代码中，我们使用了一个优先队列来存储待扩展的节点，每次从队列中取出代价最小的节点进行扩展。同时，我们使用一个集合来记录已经访问过的节点，避免了重复访问。在扩展节点时，我们通过循环遍历该节点的所有子节点，并计算新路径的代价，然后将其加入到优先队列中。同时，我们也使用了一个剪枝策略，即如果新路径的代价已经大于当前最优解，则不进行扩展。

在测试案例中，我们定义了一个简单的无向图，并从节点A到节点G求解最短路径。运行结果为`(9, ['A', 'C', 'F', 'G'])`，表示从节点A到节点G的最短路径为A->C->F->G，路径长度为9。