如何基于字典形式邻接表，寻找从节点A到宝藏节点的最短路径

你的邻接表是带权重的有向图，普通BFS只适用于无权图的最短路径，这里推荐用Dijkstra算法求全局最短路径（因为所有边权重都是正数），也可以用DFS遍历所有路径后筛选最短的，下面是具体实现：

方法一：Dijkstra算法（高效最优） #

这是处理正权图最短路径的标准算法，能快速定位到最短路径，无需遍历所有可能路径。

代码实现 #

import heapq

def find_shortest_path(adj_list, start, treasure_flag='treasure'):
    # 初始化距离字典：起点距离为0，其余设为无穷大
    distances = {node: float('inf') for node in adj_list}
    start_node = start.lower()
    distances[start_node] = 0
    
    # 前驱节点字典，用于回溯路径
    predecessors = {node: None for node in adj_list}
    
    # 优先队列（小顶堆），每次取距离起点最近的节点处理
    heap = []
    heapq.heappush(heap, (0, start_node))
    
    treasure_node = None
    
    while heap:
        current_dist, current_node = heapq.heappop(heap)
        
        # 找到宝藏节点，终止遍历
        if adj_list[current_node] == [treasure_flag]:
            treasure_node = current_node
            break
        
        # 当前路径不是最短，跳过
        if current_dist > distances[current_node]:
            continue
        
        # 遍历所有邻居，更新最短距离
        for neighbor, weight in adj_list[current_node]:
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                predecessors[neighbor] = current_node
                heapq.heappush(heap, (new_dist, neighbor))
    
    # 回溯生成路径
    path = []
    if treasure_node:
        current = treasure_node
        while current is not None:
            path.append(current.upper())
            current = predecessors[current]
        path.reverse()
    
    return path, distances[treasure_node] if treasure_node else None

# 你的邻接表
adjacency_list = {
    'a': [['b', 5], ['c', 2]],
    'b': [['e', 1], ['d', 7]],
    'c': [['d', 7]],
    'e': [['f', 2]],
    'd': [['f', 2]],
    'f': ['treasure']
}

# 调用函数
shortest_path, total_weight = find_shortest_path(adjacency_list, 'A')
print(f"最短路径: {' -> '.join(shortest_path)}")
print(f"总权重: {total_weight}")

运行结果 #

最短路径: A -> B -> E -> F
总权重: 8

方法二：DFS遍历所有路径后筛选最短 #

如果需要先获取所有可能路径再找最短，用深度优先搜索遍历所有路径，再比较权重即可：

代码实现 #

def find_all_paths(adj_list, start, treasure_flag='treasure'):
    start_node = start.lower()
    all_paths = []
    
    def dfs(current_node, current_path, current_weight):
        # 遇到宝藏节点，记录路径和权重
        if adj_list[current_node] == [treasure_flag]:
            all_paths.append((current_path + [current_node.upper()], current_weight))
            return
        # 递归遍历所有邻居
        for neighbor, weight in adj_list[current_node]:
            dfs(neighbor, current_path + [current_node.upper()], current_weight + weight)
    
    dfs(start_node, [], 0)
    return all_paths

# 获取所有路径并筛选最短
all_paths = find_all_paths(adjacency_list, 'A')
print("所有路径及权重:")
for path, weight in all_paths:
    print(f"{' -> '.join(path)}，总权重: {weight}")

all_paths.sort(key=lambda x: x[1])
shortest_path_dfs, min_weight = all_paths[0]
print(f"\n最短路径: {' -> '.join(shortest_path_dfs)}，总权重: {min_weight}")

运行结果 #

所有路径及权重:
A -> B -> E -> F，总权重: 8
A -> B -> D -> F，总权重: 14
A -> C -> D -> F，总权重: 11

最短路径: A -> B -> E -> F，总权重: 8

内容的提问来源于stack exchange，提问作者farptarp