How Complex Is the Union Operation in Pathfinding Algorithms?

[evinda]

Hello!

We have a directed graph $$G=(V,E)$$,at which each edge $$(u, v) \in E$$ has a relative value $$r(u, v) \in R$$ and $$0 \leq r(u, v) \leq 1$$, that repsesents the reliability , at a communication channel, from the vertex $$u$$ to the vertex $$v$$. Consider as $$r(u, v)$$ the probability that the chanel from $$u$$ to $$v$$ will not fail the transfer and that the probabilities are independent.
I want to write an efficient algorithm that finds the most reliable path between two given nodes.

I have tried the following:

DIJKSTRA(G,w,s,t)
  INITIALIZE-SINGLE-SOURCE(G,s)
  S=Ø
  Q=G.V
  while Q != Ø
         u<-EXTRACT-MAX(Q)
         if (u=t) return d[t]
         S<-S U {u}
         for each vertex v in  G.Adj[u]
             RELAX(u,v,w)INITIAL-SINGLE-SOURCE(G,s)
 for each vertex v  in  V.G
      d[v]=-inf
      pi[v]=NIL
 d[s]=0
RELAX(u,v,w)
  if d[v]<d[u]*w(u,v)
    d[v]<-d[u]*w(u,v)
    pi[v]<-u

and I wanted to find the complexity of the algorithm.
The time complexity of INITIALIZE-SINGLE-SOURCE(G,s) is O(|V|).
The time complexity of the line 4 is O(1).
The time complexity of the line 5 is O(|V|).
The time complexity of the line 7 is O(log(|V|)).
The time complexity of the line 8 is O(1).
Which is the time complexityof the command S<-S U {u} ?
The line 10 is executed in total $$O(\sum_{v \in V} deg(v))=O(E)$$ times and the time complexity of RELAX is O(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?

 

[Future Bruno]

The time complexity of the union is O(|V|). Therefore, the overall time complexity of the algorithm is O(|V| + E).