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

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 - 是多条边
• 初始化 - 单一 - Source(G,s) 的运行时间为 O(V)
• 主要问题是双for循环:双for循环的运行时间是O(V + E)。但我不明白，为什么不是 O(V*E)？因为对于每个顶点，我们都经过每条边，通常一个嵌套循环(总共 2 个 for 循环)的复杂度为 O(N^2)，但在这种情况下并非如此。

Answer 1

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

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