OJ Board

How to find a shortest simple path from v to u that passes
through a vertex w

You could look at your problem as finding a pair of vertex-disjoint paths from w to vertices u and v, which have minimum sum of lengths. The latter problem can be solved with min-cost max-flow.

Thanks for quick reply.
I've read in a paper that there is a O(V^2) algorithm

Min-cost max-flow can be implemented to run in O(V^2) time for this problem - it'll basically be just two Dijkstra's.
And with heaps it'll be even faster - O(E log V) with binary, and O(E + V log V) with Fibonacci heaps.

mf can you explain how to reduce this problem to min-cost max-flow ?

For each vertex x of the original graph, add vertices x_in and x_out to the flow network, and an edge (x_in, x_out) of capacity 1 and cost 0. (This is a standard trick to add capacities on vertices.)

For each edge (x, y) of the original graph of cost w, add edges (x_out, y_in) and (y_out, x_in) of cost w and capacity 1 to the flow network.

Add a source vertex s, and sink t to the network, and edge (s, w_out) of cost 0, capacity 2, and edges (u_in, t), (v_in, t) of cost 0, capacity 1.

And finally try to find a minimum-cost maximum-flow between s and t. If its value is 2, then the solution is possible, and the flow cost is the cost of shortest path from u to v thru w.

what if the graph is directed ?

It doesn't really matter if the graph is directed. The only consequences is that some edges in the graph for mincost-maxflow is missing.

it does matter. Consider graph: v --> w --> u, then we have only (v_out, w_in), (w_out, u_in) (v_out, t) (u_out, t) edges all with capacity 1 and (s, w_out, 2) - no flow of size 2 exists, but the required path does.

sure it does, u->w give 1 unit, w->v give another 1 unit of flow.
we need to have a connection to sink at w, and connection to source at w.

Moreover, any path from u->w can't overlap with any path from w->v because all vertex has capacity 1.

sclo wrote:we need to have a connection to sink at w, and connection to source at w.

That's not going to work, max flow could give you two disjoint paths: from w to itself, and from u to v.

mf wrote:

sclo wrote:we need to have a connection to sink at w, and connection to source at w.

That's not going to work, max flow could give you two disjoint paths: from w to itself, and from u to v.

There's no way to go through w explicitly, that would only give flow of 1
What I mean is this:
source->u_in->u_out->w_in->sink
source->w_out->v_in->v_out->sink

additional arcs are:
u_out->v_in

Notice that w_in->w_out is not in the graph.

There could be a directed cycle in graph, which includes w, and if you have a source at w_out, and a sink at w_in, max flow could push flow from w_out to w_in along this cycle. And if there's also some other path from u to v, max flow will find it too, and give a flow of value 2.

mf wrote:There could be a directed cycle in graph, which includes w, and if you have a source at w_out, and a sink at w_in, max flow could push flow from w_out to w_in along this cycle. And if there's also some other path from u to v, max flow will find it too, and give a flow of value 2.

So how can this problem be fixed?

Is there any problems to apply mf idea on it. I am interested with this problem.