我正在修改单源最短路径算法，在视频中，老师提到BFS/DFS不能直接用于查找最短路径 in a 加权图（我想每个人都知道这一点）并说自己找出原因。
我想知道为什么它不能用于加权图的确切原因/解释。是由于边缘的重量还是其他原因造成的？有人可以解释一下我吗，因为我感到有点困惑。
PS：我经历过this https://stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path-java问题和this https://cs.stackexchange.com/questions/18138/dijktra-algorithm-vs-breath-first-search-for-shortest-path-in-graph问题。
考虑这样的图表：
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 个。
您可以使用迪杰斯特拉算法 http://en.wikipedia.org/wiki/Dijkstra's_algorithm而不是 BFS 来寻找加权图上的最短路径。从功能上来说，该算法与BFS非常相似，并且可以用与BFS类似的方式编写。唯一改变的是您考虑节点的顺序。
例如，在上图中，从 A 开始，BFS 将处理 A --> B，然后 A --> C，并在那里停止，因为所有节点都已被看到。
另一方面，Dijkstra 算法的运行过程如下：
- 考虑 A --> C（因为这是 A 中的最低边权重）
- 考虑 C --> B （因为这是我们迄今为止到达的任何节点的最低权重边，我们尚未考虑）
- 考虑并忽略 A --> B，因为 B 已经被看到。
请注意，区别仅在于order其中检查边缘。 BFS 会考虑all在移动到其他节点之前从单个节点删除边，而 Dijkstra 算法将始终考虑重量最低的unseen边，来自连接到的边集到目前为止见过的所有节点
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
