Multiple source shortest path with one reversal [closed]

Question

Lets say we have a directed graph G, with vertices V, that have lengths l.

I need to find the shortest path between every ordered pair of vertices in the graph, with the following constraint:

In a path from v_i to v_j, you are allowed to go backwards along an edge, at most once. By backwards along an edge, I mean going from v_q->v_r when the edge is actually v_r->v_q.

Formally stated: On a path from v_i to v_j you could go from v_q to v_r backwards along edge (v_r, v_q), at a cost of l(v_r, v_q), at most once, and forwards on every other edge (v_x, v_y) in the path, at a cost of l(v_x, v_y).

Any help would be appreciated.

Answer 1

You can start by converting your graph $G = (V, E)$ into a new graph $G'$ as follows:

The vertices of $G'$ should be $V \times \{0,1\}$. For every vertex $v \in V$, include the edge from $(v, 0)$ to $(v, 1)$ with weight zero. For every edge $(u,v) \in E$ with weight $l$, include the edge from $(u,0)$ to $(v,0)$, the edge from $(u,1)$ to $(v,1)$, and the edge from $(v,0)$ to $(u,1)$, each with weight $l$.

Then the shortest path in $G$ from $v_i$ to $v_j$ with at most one edge reversal corresponds to the shortest path in $G'$ from $(v_i, 0)$ to $(v_j, 1)$:

In general, each path in $G'$ which starts in $V \times \{0\}$ and ends in $V \times \{1\}$ consists of a path in $V \times \{0\}$ followed by one edge between the two halves of the graph followed by a path in $V \times \{1\}$. The paths in $V \times \{0\}$ and in $V \times \{1\}$ are exactly the same as paths in $G$ (since those two sets of vertices each induce $G$ as the induced subgraph of $G'$). The edge between the two paths must be one of two possibilities: either it is a zero cost edge from $(v, 0)$ to $(v, 1)$ (i.e. staying at the "same" vertex at zero cost) or it is a weight $l$ edge from $(v,0)$ to $(u,1)$ where $(u,v) \in E$ has weight $l$ (i.e. traversing one edge backwards)

So to solve your problem, you can just solve all-pairs shortest path in $G'$ and then take the shortest path from $(v_i, 0)$ to $(v_j, 0)$ as the shortest at-most-one-reversal path from $v_i$ to $v_j$ in $G$.