Given a weighted(Positive weights) undirected graph G(V,E)...we are given two vertices s,t belongs to V. we have to find two new edges from a list of available edges((a1,b1)...(ak,bk)) to add to tha graph such that the distance between s and t is minimised as much as possible. The weights of new edges are all positive as well..
the direct approach would be two select all possible pairs of new edges and find shortest distance with it. the time complexity for this approach is quadratic k. i want an algorithm with better time complexity .. please help me on this ..thanks
A useful edge must shorten the distance between its vertices.
LOOP over K
Find S shortest path between ak and bk in G
IF new edge weight is greater or equal, discard (ak,bk)
APPLY direct algorithm on remaining available edges.