I have the following code:
for each nodeG in Graph
for each nodeS in subset
path(nodeG, nodeS) // using dijkstra that in the best has O(V lg V + E);
end
end
Every time the main loop executes, one vertex is extracted from the queue. Assuming that there are V vertices in the graph, the queue may contain O(V) vertices. Each pop operation takes O(lg V) time assuming the heap implementation of priority queues. So the total time required to execute the main loop itself is O(V lg V). In addition, we must consider the time spent in the function expand, which applies the function handle_edge to each outgoing edge. Because expand is only called once per vertex, handle_edge is only called once per edge. It might call push(v'), but there can be at most V such calls during the entire execution, so the total cost of that case arm is at most O(V lg V). The other case arm may be called O(E) times, however, and each call to increase_priority takes O(lg V) time with the heap implementation. Therefore the total run time is O(V lg V + E lg V), which is O(E lg V) because V is O(E) assuming a connected graph.
(There is another more complicated priority-queue implementation called a Fibonacci heap that implements increase_priority in O(1) time, so that the asymptotic complexity of Dijkstra's algorithm becomes O(V lg V + E); however, large constant factors make Fibonacci heaps impractical for most uses.)
So basically now for the two for each, we have O(n^2). But the path is actually Dijkstra's Algorithm where Big Oh is O(V lg V + E). How can I multiply this to the total Big Oh?
I understand your question like this (correct me if I'm wrong):
You try to compute Dijkstra for every pair of nodes in a graph. So you have V(V-1)/2 pairs in the graph (V is number of vertices).
Then, V(V-1) (that is O(V^2) times you compute Dijkstra, which has complexity O(V + ElogV) (I don't know where did you get your O(VlogV + E) from, but it's probably incorrect)
Overall, the complexiy is O(V^2logV + EV^2)