有向无圈图算法中单源最短路径的运行时间

Question

以下是算法：

Topologically sort the Vertices of G
Initialize - Single - Source(G,s)
for each vertex u, taken in topologically sorted order
     for each vertex v in G.Adjacent[u]
         Relax(u,v,w) 

• 拓扑排序有运行时O(V + E)，其中V-是顶点数，E-是若干边
• 初始化-单源(G，s)具有运行时O(V)
• 主要问题是双循环:双循环的运行时间为O(V + E)。但我不明白，为什么不是O(V*E)？因为对于每个顶点，我们都要遍历每条边界，通常情况下，一个嵌套循环(所有循环都是2)的复杂度为O(N^2)，但在这种情况下不是这样的。

Answer 1

对于每个顶点u，您只迭代从u输出的边，每个不同的边只被访问一次，这就是为什么算法需要O(V+E)时间。

这假设您使用的是图表示(例如邻接列表，而不是矩阵)，它允许快速访问每个顶点的相邻边缘。拓扑排序也需要这个。