algorithm - Time complexity of union -

we have directed graph g=(v,e) ,at each edge (u, v) in e has relative value r(u, v) in r , 0<=r(u, v) <= 1, represents reliability , @ communication channel, vertex u vertex v.

consider r(u, v) probability chanel u v not fail transfer , probabilities independent. want write efficient algorithm finds reliable path between 2 given nodes.

i have tried following:

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.         each vertex v in  g.adj[u] 9.             relax(u,v,r)   initial-single-source(g,s) 1. 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 

and wanted find complexity of algorithm.

the time complexity of initialize-single-source(g,s) o(|v|). time complexity of line 4 o(1). time complexity of line 5 o(|v|). time complexity of line 7 o(log(|v|)). time complexity of line 8 o(1). time complexityof command s<-s u {u} ? line 10 executed in total o(Σ_{v \in v} deg(v))=o(e) times , time complexity of relax o(1).

so time complexity of algorithm equal time complexity of lines (3-9)+o(e). time complexity of union?

so time complexity of algorithm equal time complexity of lines (3-9)+o(e). time complexity of union?

no, not complexity of union, union can done pretty efficiently if using hash table example. moreover, since use s union, seems redundant.

the complexity of algorithm depends heavily on extract-max(q) function (usually logarithmic in size of q, logv per iteration), , on relax(u,v,r) (which logarithmic in size of q, since need update entries in priority queue).

as expected, brings same complexity of original dijkstra's algorithm, o(e+vlogv) or o(elogv), depending on implementation of priority queue.