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 l...