Given a weighted directed graph $$$G$$$ and $$$2$$$ different vertices $$$s$$$ and $$$t$$$ in it. How can we find all edges $$$e$$$ such that removing $$$e$$$ increases the distance between $$$s$$$ and $$$t$$$? Is there a better way then $$$O(E*E*log(V))$$$ time method where we test each edge by removing it? Can we also find all vertices $$$v$$$ defined analogously?
Auto comment: topic has been updated by frying_pan (previous revision, new revision, compare).
Auto comment: topic has been updated by frying_pan (previous revision, new revision, compare).
let d1[i] be the minimum distance from s to i.
let c1[i] be the number of paths whose distance from s to i equal to d1[i].
let d2[i] be the minimum distance from i to t.
let c2[i] be the number of paths whose distance from i to t equal to d2[i].
let "t" be the minimum distance from s to t.
let "num" be the number of shortest paths from s to t.
we will count the number of edges (u->v) that d1[u] + d2[v] + len of edge(u->v) == t and d1[u] * d2[v] == num
This algorithm is correct, but when there are many edges in the graph the number of shortest paths may be too large to store efficiently, and using modulo will lead to some false equalities.
One possible idea is to construct the "shortest-path graph" between S and T (there might be a better name for this, but it will do for now). This graph consists of all edges that lie on some shortest path between S and T (and their endpoints as nodes). We can compute this graph by running Dijkstra's algorithm twice — once from S and once from T. (when running from T, you will need to invert the edges.) Then, an edge's removal will increase the distance from S to T if and only if it is a bridge in this "shortest-path graph". You can find those bridges with the standard algorithm.
To find the nodes that increase the distance, you can find the articulation points in this graph.
Now special edges are essentially edges through which all paths from $$$s$$$ to $$$t$$$ in $$$G$$$ pass.
How do we check if an edge $$$E : (u\rightarrow v)$$$ in $$$G$$$ is special? There is just one condition:
Consider all edges (except for $$$E$$$) $$$(x \rightarrow y)$$$ in $$$G$$$ such that $$$dis(s, x) <= dis(s, u)$$$. Then $$$max(dis(s, y))$$$ over all such $$$(x \rightarrow y)$$$ must be $$$\leq dis(s, u)$$$.
This can be easily be checked by maintaining the two largest $$$dis(s, y)$$$ encountered.
So both the problems can be easily solved in $$$O(n\log{n})$$$.
In the shortest-path graph all edges are directed away from S and towards T, so if an edge is a bridge when you undirect the edges it will also be a bridge in the DAG.
Interesting question, I don't know the answer but I like to suggest a similar problem: https://codeforces.net/gym/101741/problem/L