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 vi to vj, you are allowed to go backwards along an edge, at most once. By backwards along an edge, I mean going from vq->vr when the edge is actually vr->vq.

Formally stated: On a path from vi to vj you could go from vq to vr backwards along edge (vr, vq), at a cost of l(vr, vq), at most once, and forwards on every other edge (vx, vy) in the path, at a cost of l(vx, vy).

Any help would be appreciated.

  • $\begingroup$ This is a nice homework problem. Thank you. $\endgroup$
    – Jeffε
    Feb 18 '17 at 18:10

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$.

  • $\begingroup$ An alternate simpler view would be to use the standard dijikstra's algorithm with an extra flag field stored along with each vertex label. This flag would indicate whether the reverse edge have been used yet (flag=1) or not (flag=0), to build the shortest path to the vertex. Hence, when a vertex is added with shortest distance from $s$, you allow two such instances to be processed one with flag 0, and one with flag 1. And whenever a vertex with flag 0 is processed, you also consider reverse edges pushing the entries of corresponding neighbours in the heap with flag 1. $\endgroup$
    – sbzk
    Feb 13 '17 at 13:12
  • $\begingroup$ Being the same in principle, its just an alternate view of the above described solution. $\endgroup$
    – sbzk
    Feb 13 '17 at 13:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.