-1
$\begingroup$

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.

$\endgroup$

closed as off-topic by Yuval Filmus, Jeffε, Hsien-Chih Chang 張顯之, David Eppstein, Yoshio Okamoto Feb 22 '17 at 0:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Yuval Filmus, Jeffε, Hsien-Chih Chang 張顯之, David Eppstein, Yoshio Okamoto
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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

$\endgroup$
  • $\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.