带权有向图的广度优先遍历

宽度优先遍历（Breadth-First Search，简称BFS）在处理带权有向图中寻找最短路径时非常有效。它的工作原理类似于我们在现实中探索迷宫时会先走离起点最近的一层，然后继续深入每一层直到找到目标位置。在这个过程中，BFS会记录每个节点到达目标所经过的最小步数。

以下是带权有向图的BFS用于求最短路径的基本步骤：

1. **初始化**：
- 创建一个队列`Q`，将起始节点`start`入队，并设置它的距离（cost）为0。
- 创建一个辅助数组`distance[]`来存储每个节点到源节点的最短距离，初始全部设为`INT_MAX`，除了起始节点外设为0。

2. **遍历**：
- 当队列不为空时，循环执行以下操作：
a. 取出队首节点`curr`，标记其已访问（例如，将其放入一个`visited`数组中）。
b. 对于`curr`的所有未访问的邻接节点，计算它们的新距离（当前节点距离加权），如果新距离小于`distance`数组中的值，更新该节点的距离，并将其加入队列。

3. **更新**：
- 每次更新完一个节点的距离后，继续检查队列内的其他节点，直到队列为空。

4. **结果查找**：
- 最终，`distance`数组中的值就是每个节点到起始节点的最短路径长度。为了得到最短路径，我们可以从目标节点开始反向追踪，记录下经过的节点序列。

5. **路径回溯**：
- 从目标节点开始，如果下一个节点距离减小，说明通过当前节点达到了更短路径，就把它加入结果路径并移动到上一个节点。重复这个过程，直至回到起点。

在实际编码中，你需要一个数据结构（如邻接列表或矩阵）来存储图的信息，并实现上述逻辑。