'shortest path between two vertices after adding two new edges in a graph
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
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|