使用BFS加权图

考虑如下图：

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的算法将如下运行：

1. 考虑A-> C（因为这是A的最低边缘权重）
2. 考虑C-> B（因为这是到目前为止我们尚未考虑的任何节点的最低权重边）
3. 考虑并忽略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代码非常相似， 唯一真正的区别是使用堆（而不是常规队列数据结构），该堆按到节点的距离排序 。