edge in all the shortest paths

[nicoletsg]

Please give in your ideas and suggestions for best algorithm on the following problems :

We have a graph G=(V,E) and a function of weight on the edges w:E->R we have a couple of two vertexes s,t and an edge e we suppose that there is not cycle with a negative weight find an algorithm that determines if there is an edge e in all the shortest paths from s to t

[mf]

First, run Dijkstra's or Bellman-Ford's algorithm (if you have negative edges) to compute dist(s, x) = length of shortest path from s to x, for all x. And do a depth-first search in G^T to determine all vertices from which t is reachable.

Then construct a subgraph H = (V', E') as follows:
V' = all vertices reachable from s and from which t is reachable,
E' = all edges (u, v) such that u and v are in V', and dist(s, u) + w(u, v) = dist(s, v).
It can be proven that the set of paths between s and t in H is exactly the set of shortest paths between s and t in G.

Next, turn H into an undirected graph and check whether it contains a bridge. It can be done in linear time with a modification of DFS. Any bridge in H will be your "edge e".

[nicoletsg]

I think this is a very smart idea! Thanks.

[corbu]

i'm thinking if we can find if there is at least one path going through a line.
my approach is to memorate all shortest path (if i use dijkstra ) in a arrays of paths
and check if the magic line is in the array.
u think it would work with negative edge ?

does anyone have other idea ?
thanks