Dijkstra's Single Source Shourtest Path with an extra edge with weight of 'w'
algorithm, data-structures, graph
Solution
There are two options:
We don't need an extra edge. This case is handled by a standard Dijkstra algorithm.
A shortest path with an extra edge looks like this: `shortest_path(start, V) + (V, U) + shortest_path(U, target)`. That is, we go from the start to some vertex `V` by the shortest path in the original graph, then we go to `U` (again, an arbitrary vertex) by adding this extra edge (`V` and `U` mustn't be connected) and then we go from `U` to the target node by the shortest path in the original graph.
We can use the structure of the path to get an `O(n ^ 2)` solution: we can compute shortest paths from the start node to all the others (one run of the Dijkstra's algorithm) and all shortest paths from the target node to all other nodes (one more run). Now we can just iterate over all possible pairs `(V, U)` and pick the best one.
Bonus: we can solve it in `O(m log n)` for a sparse graph. The idea is as follows: instead of checking all `(U, V)` pairs, we can find such `U` that it has the minimal distance to the target among all vertices that are not connected to `V` in `degree(V) * log V` (or even linear) time (this problem is known as finding the smallest element not in the set).
Problem
In an recent interview I was asked to implement single source shortest path algorithm(for undirected and positive weighted graph) with slight modification i.e. we're given an extra edge with weight 'w'. And we have to find if we can find a more shorter path, than the one calculated by SSSP algo, by connecting that extra edge, with weight 'w', between two nodes which are not already connected. Here's an image. As according to SSSP the shortest path between A(source) & D(destination)is A-B-C-D i.e. total of 8. But given the extra edge. It can be connected between A and D, which are not already connected, to minimize the shortest path yielded through SSSP algo. Image of graph with extra edge contributing the shortest path I tried thinking about the solution. But nothing struck so far. I've implemented the Dijkstra algorithm to find the shortest path. But this little modification has baffled me. So can you help a little bit.