联合的时间复杂度

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

我认为解决方案应该基于经典的 Dijkstra 算法（其复杂性众所周知），正如您所建议的那样，但是在您的解决方案中，您对 "shortest path" 问题的定义不正确。

请注意，A 和 B 的概率是 p(A) * p(B)（如果它们是独立的）。因此，您应该找到一条路径，其边的倍增是最大化。而 Dijkstra 算法找到其 sum 边为 minimized.

的路径

要克服这个问题，您应该将边的权重定义为：

R*(u, v) = -log ( R(u, v) )

通过引入对数，您将乘法问题转换为加法问题。

Answer 2

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?

不，这不是并集的复杂性，例如，如果您使用散列 table，则可以非常有效地完成并集。此外，由于您仅将 S 用于联合，因此它似乎是多余的。

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

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

联合的时间复杂度

Time complexity of union

algorithm

union

dijkstra

time-complexity