最优路径广度优先算法怎么编写代码
时间: 2023-07-26 17:12:24 浏览: 44
最优路径广度优先算法的代码实现可以使用队列来存储待访问节点。下面是一个简单的 Python 实现:
```python
from queue import Queue
def bfs_shortest_path(graph, start, end):
# 初始化队列和 visited 数组
q = Queue()
visited = set()
# 将起点加入队列
q.put((start, [start], 0))
# 开始搜索
while not q.empty():
node, path, dist = q.get()
visited.add(node)
# 找到目标节点
if node == end:
return path, dist
# 将相邻节点加入队列
for neighbor, weight in graph[node]:
if neighbor not in visited:
q.put((neighbor, path + [neighbor], dist + weight))
# 没有找到目标节点
return None
```
其中,`graph` 是一个字典,表示图的邻接表,每个节点对应的值是一个包含相邻节点和边权值的元组列表;`start` 和 `end` 分别表示起点和终点。搜索过程中,每个节点都被表示为一个元组 `(node, path, dist)`,其中 `node` 是节点标识,`path` 是从起点到该节点的路径,`dist` 是从起点到该节点的距离。在每次加入队列时,需要将路径和距离更新。最后,如果找到目标节点,返回路径和距离;否则返回 `None`。