如何遍历图并返回最短路径？求简便实现方案

当然有啦！对于这种无权重的图，**广度优先搜索（BFS）**就是最适合的简便实现方式——它天然能保证找到的第一条路径就是最短路径，完全匹配你的需求。

下面直接给出可运行的代码实现，完全贴合你的示例要求：

from collections import deque

def travel(start, end, path_dict):
    # 处理起点和终点相同的特殊情况
    if start == end:
        return {'path': [start], 'length': 0}
    
    # 初始化队列，每个元素是(当前节点字符串, 当前路径列表)
    queue = deque()
    queue.append((str(start), [start]))
    # 记录已访问节点，避免循环
    visited = set()
    visited.add(str(start))
    
    while queue:
        current_node, current_path = queue.popleft()
        # 遍历当前节点的所有邻接节点
        for neighbor in path_dict[current_node]:
            neighbor_int = int(neighbor)
            # 找到终点，直接返回结果
            if neighbor_int == end:
                return {
                    'path': current_path + [neighbor_int],
                    'length': len(current_path)
                }
            # 未访问过的节点，加入队列继续遍历
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, current_path + [neighbor_int]))
    
    # 如果终点不可达（你的示例里没这种情况，做个兜底）
    return {'path': [], 'length': -1}

# 测试你的示例
path_dict={ '0':['5'], '1':['4','5'], '2':['1','3','4'], '3':['1','4'], '4':['1'], '5':['0','2','3','4'], }
print(travel(1,5))  # 输出: {'path': [1, 5], 'length': 1}
print(travel(0,2))  # 输出: {'path': [0, 5, 2], 'length': 2}
print(travel(4,0))  # 输出: {'path': [4, 1, 5, 0], 'length': 3}

代码关键点说明： #

• 使用deque实现队列：因为BFS需要频繁从队头取出元素，deque.popleft()是O(1)操作，比列表的pop(0)（O(n)）高效很多。
• 路径实时记录：每个队列元素都带着从起点到当前节点的完整路径，这样一旦找到终点，就能直接拼接出最短路径，不用事后回溯。
• 字符串转整数：你的邻接表键是字符串类型，所以处理时需要转成整数和输入的起点/终点匹配。
• 已访问集合：避免重复访问节点，防止出现循环遍历的情况。

这个实现逻辑清晰，代码量不大，完全满足你的需求，而且时间复杂度在无权重图里是最优的~

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