考虑如下图：
A---(3)-----B
| |
\-(1)-C--(1)/
从A到B的最短路径是通过C（总重量为2）。正常的BFS将直接采用从A到B的路径，如图所示标记为B，从A到C的标记路径为C。
在下一阶段，从C传播，B已标记为可见，因此从C到B的路径将不被视为潜在的较短路径，并且BFS会告诉您从A到B的最短路径具有权重的3。
您可以使用Dijkstra的算法而不是BFS在加权图上找到最短路径。在功能上，该算法与BFS非常相似，并且可以通过与BFS类似的方式编写。唯一改变的是您考虑节点的顺序。
例如，在上图中，从A开始，BFS将处理A-> B，然后处理A-> C，并在那里停止，因为已经看到了所有节点。
另一方面，Dijkstra的算法将如下运行：
注意，差异仅在于检查边缘的 顺序 。BFS将考虑单个节点的 所有 边缘，然后再转移到其他节点，而Dijkstra的算法将始终考虑 连接到 _ *_。 听起来令人困惑，但是伪代码非常简单：
create a heap or priority queue
place the starting node in the heap
dist[2...n] = {∞}
dist[1] = 0
while the heap contains items:
vertex v = top of heap
pop top of heap
for each vertex u connected to v:
if dist[u] > dist[v] + weight of v-->u:
dist[u] = dist[v] + weight of edge v-->u
place u on the heap with weight dist[u]
Wikipedia的此GIF可以很好地显示发生的情况：
请注意，这看起来与BFS代码非常相似， 。
602392714
清零编程群