为什么 Dijkstra 算法（最短路径）的时间复杂度与 DFS 不同？
Why isnt Dijkstra's algorithm's (for shortest path) time complexity the same as DFS?
Dijkstra 的算法不能使用跟踪当前路径长度的 DFS 来实现，每次到达未访问的节点时，它都会更新到该节点的最短路径的长度，如果到达的节点已经访问过，如果当前长度小于节点中的长度，则更新长度？
这只是 DFS，这意味着 运行 时间应该是线性的 (O(|V| + |E|))。
当你到达一个被访问的节点A时，假设当前路径的长度比A中的长度短，所以你将长度更新为A。但是那些与A连接的节点呢？你也需要更新它们，但你不能，因为 A 已经被访问过。
总之，运行时间是线性的，但算法不正确
我们以这张图为例，搜索应该从a开始，目标节点是c:
DFS
假设一个节点的子节点是按词法顺序遍历的，DFS将按a、b、c、d、e的顺序访问节点
它将找到这些距离：
a: 0
b: 5
c: 13
d: 8
然后从d又会看到c，更新为12
接下来是：
e: 1
从 e 它将再次看到 b，并将其更新为 3。但是 DFS 也没有看到影响此更改在节点 c 和 d.
上发生
迪杰斯特拉
另一方面，Dijkstra 算法将按以下顺序访问节点：
a: 0
e: 1
b: 3
然后会取权重为5的边，但是看到b已经被访问过，忽略它。那么：
d: 6
c: 10
...并且找到了距离正确的目标。
BFS
只是回答你下面的评论：BFS 也不会找到正确的路径，因为 BFS 没有考虑（总）权重；它只是最小化路径上的边数。
BFS会这样访问节点：
a: 0
b: 5
e: 1
c: 13
...它会停在那里。如果您不停止，而是继续（可能会覆盖），则该过程将继续：
d: 8
然后它从 e 中看到 b，并更新：
b: 3
然而，由于 b 已经被访问过，BFS 将看不到此更改对 c 和 的影响d.
它也从d中看到c并更新c为12。然后有BFS 无事可做，显然结果是错误的。
Dijkstra 的算法不能使用跟踪当前路径长度的 DFS 来实现，每次到达未访问的节点时，它都会更新到该节点的最短路径的长度，如果到达的节点已经访问过，如果当前长度小于节点中的长度，则更新长度？
这只是 DFS，这意味着 运行 时间应该是线性的 (O(|V| + |E|))。
当你到达一个被访问的节点A时，假设当前路径的长度比A中的长度短，所以你将长度更新为A。但是那些与A连接的节点呢？你也需要更新它们，但你不能，因为 A 已经被访问过。
总之，运行时间是线性的，但算法不正确
我们以这张图为例，搜索应该从a开始，目标节点是c:
DFS
假设一个节点的子节点是按词法顺序遍历的，DFS将按a、b、c、d、e的顺序访问节点
它将找到这些距离：
a: 0
b: 5
c: 13
d: 8
然后从d又会看到c，更新为12
接下来是：
e: 1
从 e 它将再次看到 b，并将其更新为 3。但是 DFS 也没有看到影响此更改在节点 c 和 d.
上发生迪杰斯特拉
另一方面，Dijkstra 算法将按以下顺序访问节点：
a: 0
e: 1
b: 3
然后会取权重为5的边，但是看到b已经被访问过，忽略它。那么：
d: 6
c: 10
...并且找到了距离正确的目标。
BFS
只是回答你下面的评论：BFS 也不会找到正确的路径，因为 BFS 没有考虑（总）权重；它只是最小化路径上的边数。
BFS会这样访问节点：
a: 0
b: 5
e: 1
c: 13
...它会停在那里。如果您不停止，而是继续（可能会覆盖），则该过程将继续：
d: 8
然后它从 e 中看到 b，并更新：
b: 3
然而，由于 b 已经被访问过，BFS 将看不到此更改对 c 和 的影响d.
它也从d中看到c并更新c为12。然后有BFS 无事可做，显然结果是错误的。