PROBLEM LINK:
Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar
DIFFICULTY:
Hard
PREREQUISITES:
Graph theory, Dijkstra’s shortest path algorithm
PROBLEM:
Given a weighted bi-directional graph, the task is to find out the shortest path length when at most a single edge is removed, the identity of which is provided by a query. Multiple such queries are made.
EXPLANATION:
Approach 1:
The simplest approach is to run Dijkstra’s algorithm for each query by removing the edge as directed, but this is not fast enough.
Optimised Solution:
We observe that unless an edge is removed which lies on ALL shortest paths from the source to the destination, the answer is simply the shortest distance from source to destination. Let us call such an critical edge a bridge.
Further, let us call an edge OPTIMAL if it lies on ANY shortest path from source to destination.
Clearly, all bridges are optimal edges. We can sort these bridges by increasing order of their distances from the source. Then we can number them by their indices, starting from 0.
Now, let us define an island i as a collection of vertices that can be reached by crossing all bridges numbered 0 to i-1 and no more, by using only the shortest path tree of our given graph with the source as root.
In case a bridge i is removed, the shortest path must utilize an edge that links any island numbered 0 to i with any island numbered greater than i.
Let us define: bypass(i) as the required answer when bridge i is removed.
Now, to determine all such bypass values, we can iterate over every edge that connects two islands i1 and i2 (clearly no optimal edge fulfils this criteria) and for every bridge i in i1 to i2-1 we set bypass(i) to the shortest path distace utilizing this edge if it is found less than the current value of bypass(i).
However, this results in an O(E^2) algorithm, and we can do better.
We can use any range update and query structure like segment tree to update the range i1 to i2-1 as required, and then query a particular i when required, both in log n time.
Now we can develop an algorithm.
First we run Dijkstra’s algorithm, once from destination and once from source. We store the paths traversed when run from source. This is required for future steps.
Find all bridges:
Consider an edge e joining vertices u and v. Now if distance between source and u + weight of e + distance between destination and v = shortest path distance between source and destination, edge e is optimal. We can then determine all the optimal vertices. Now we know that each bridge lies on all shortest paths from source to destination, thus an optimal edge at a unique distance from the source and destination must be a bridge. Thus we can sort the list of optimal edges and find out the bridges.
Identifying islands:
To identify islands, first we construct the shortest path tree. Now we can simply traverse this tree, and assign an island number to each vertex by counting the number of bridges crossed to get to that vertex.
Getting bypass values:
Iterate over all non-optimal edges. For each such edge e connecting island i1 and i2, range update bypass(i) for all i in i1 to i2-1 as required using a preferred data structure.
Now it’s a simple matter to answer queries. If the removed edge is bridge i, query the data structure with i and print the value, else simply print the shortest path distane between source and destination
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.