考虑如下图：
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的算法将如下运行：
- 考虑A-> C（因为这是A的最低边缘权重）
- 考虑C-> B（因为这是到目前为止我们尚未考虑的任何节点的最低权重边）
- 考虑并忽略A-> B，因为已经看到了B。
注意，差异仅在于检查边缘的 顺序 。BFS将考虑单个节点的 所有 边缘，然后再转移到其他节点，而Dijkstra的算法将始终考虑 连接到 _迄今为止已看到的所有节点* _的一组边缘中 _权重最小的 未看见 边缘 *_。 听起来令人困惑，但是伪代码非常简单：
create a heap or priority queueplace the starting node in the heapdist[2...n] = {∞}dist[1] = 0while 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-->uplace u on the heap with weight dist[u]Wikipedia的此GIF可以很好地显示发生的情况：
请注意，这看起来与BFS代码非常相似， 唯一真正的区别是使用堆（而不是常规队列数据结构），该堆按到节点的距离排序 。
