algorithm - 联合的时间复杂度

Question

我们有一个有向图 G=(V,E) ，其中 E 中的每条边 (u, v) 在 R 中都有一个相对值 r(u, v) 并且 0<=r(u, v) < = 1，表示在通信信道上，从顶点 u 到顶点 v 的可靠性。

将 r(u, v) 视为从 u 到 v 的信道传输不会失败的概率，并且概率是独立的。 我想编写一个高效的算法来找到两个给定节点之间最可靠的路径。

我尝试了以下方法:

DIJKSTRA(G,r,s,t)
1.  INITIALIZE-SINGLE-SOURCE(G,s)
2.  S=Ø
3.  Q=G.V
4.  while Q != Ø
5.         u<-EXTRACT-MAX(Q)
6.         if (u=t) return d[t]
7.         S<-S U {u}
8.         for each vertex v in  G.Adj[u]
9.             RELAX(u,v,r)


INITIAL-SINGLE-SOURCE(G,s)
1. for each vertex v  in  V.G
2.      d[v]=-inf
3.      pi[v]=NIL
4. d[s]=1



RELAX(u,v,r)
 1. if d[v]<d[u]*r(u,v)
 2   d[v]<-d[u]*r(u,v)
 3.   pi[v]<-u

我想找出算法的复杂性。

INITIALIZE-SINGLE-SOURCE(G,s)的时间复杂度为O(|V|)。 第 4 行的时间复杂度为 O(1)。 第5行的时间复杂度是O(|V|)。 第 7 行的时间复杂度为 O(log(|V|))。 第8行的时间复杂度是O(1)。 命令 S<-S U {u} 的时间复杂度是多少？ 第10行一共执行了O(Σ_{v\in V} deg(v))=O(E)次，RELAX的时间复杂度为O(1)。

所以算法的时间复杂度等于第(3-9)行的时间复杂度+O(E)。 联合的时间复杂度是多少？

Answer 1

So the time complexity of the algorithm is equal to the time complexity of the lines (3-9)+O(E). Which is the time complexity of the union?

不，这不是联合的复杂性，如果您使用哈希表，联合可以非常有效地完成。此外，由于您仅将 S 用于联合，因此它似乎是多余的。

算法的复杂性在很大程度上还取决于您的EXTRACT-MAX(Q) 函数(通常它是Q 大小的对数，因此每次迭代的 logV )，以及 RELAX(u,v,r)(通常也是 Q 大小的对数，因为您需要更新优先级队列中的条目)。

正如预期的那样，这给我们带来了与原始 Dijkstra 算法相同的复杂性，即 O(E+VlogV) 或 O(ElogV)，具体取决于实现你的优先队列。