联合时间复杂性

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

我想找出算法的复杂性。

初始化单源(G，s)的时间复杂度为O(x=0).第4行的时间复杂度是O(1)。第5行的时间复杂性是O({x}})。第7行的时间复杂度为O(log(Log))。第8行的时间复杂度是O(1)。哪个是命令S<-S {u}的时间复杂性？第10行执行总O(Σ_{v \in V} deg(v))=O(E)倍，RELAX的时间复杂度为O(1)。

因此，算法的时间复杂度等于线(3-9)+O(E)的时间复杂度。哪个是联盟的时间复杂性？

Answer 1

因此，算法的时间复杂度等于线(3-9)+O(E)的时间复杂度。哪个是联盟的时间复杂性？

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

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

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

Answer 2

我认为解决方案应该基于经典的Dijkstra算法(其复杂性是众所周知的)，正如您建议的那样，但是在您的解决方案中，您错误地定义了“最短路径”问题。

注意，A和B的概率是p(A) * p(B) (如果它们是独立的)。因此，您应该找到一条路径，其边的multiplication是最大化的。而Dijkstra算法寻找边的和为最小化的路径。

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

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

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