Is there an edge whose removal will extend the shortest path? - graph problem

Question

Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal will result in the shortest path from $s$ to $t$ being extended (and if so returns this edge). We may remove only one edge.

In practice, a graph is given as a list of lists. The $i$-th list contains the numbers of vertices adjacent to the $i$-th vertex (numbered from 0).

Example:
$G = [ [1,2], [0,2], [0,1] ]$
$s = 0$
$t = 2$

The answer is an edge terminated by vertices 0 and 2 - the shortest path has been extended from 1 to 2.

How can this problem be solved in optimal time?

All I know is that the best way to find the shortest path in a basic graph like this is to just use BFS, and I guess I have to use it somehow here as well, but otherwise I have no idea how to approach this...

Answer 1

the Idea

Find all edges that are on one of the shortest paths from $s$ to $t$. Find the bridges in the graph that consists of those edges.

the Approach

1. Use breadth-first-search to compute $d_s(u)$, the distance from $s$ to $u$ for each vertex $u$. If $t$ is found not reachable from $s$, return nothing.
2. Ditto for $d_t(v)$.
3. Collect all edges $(u,v)$ such that $d_s(u) + d_t(v) = d_s(t)-1$ as graph $S$.
4. Try running a linear algorithm that finds all bridges in $S$ such as this one. As soon as one bridge has been found, return it.
5. Return nothing.

An algorithm that implements the approach above runs in linear time.