拓扑排序为什么要找最短路径O(V+E)

Question

我很困惑为什么最短路径的拓扑排序是 O(V+E) 的大 O。 这是算法：

1. Topologically sort G into L;
2. Set the distance to the source to 0;
3. Set the distances to all other vertices to infinity;
4. For each vertex u in L
5.    - Walk through all neighbors v of u;
6.    - If dist(v) > dist(u) + w(u, v) 
7.       - Set dist(v) <- dist(u) + w(u, v);

在我看来它是 O(V*E) 而不是 O(V+E) 因为它有 2 个嵌套的 for 循环。但根据维基百科，它是 O(V+E)，我在这里遗漏了什么吗？ https://en.wikipedia.org/wiki/Topological_sorting#Application_to_shortest_path_finding

Answer 1

请记住边是有向的，因此绝不会为多个顶点考虑同一条边。尽管有嵌套循环，您最终还是只查看了每个顶点和每条边一次。