<p>Let $P_{1}$, $P_{2}$ be two paths in a undirected unweighted graph $G=(V,E)$. We want to minimize the following quantity:</p>

<p>$ C = min_{P_{1},P_{2} \; paths \; in \; G} \{ |P_{1}| + |P_{2}| + |P_{1} \cap P_{2}| \}$. </p>

<p>Also suppose $L$ is the length of the shortest path in $G$, i.e. $L = min_{P \; path \; in \; G} \{ |P| \}$</p>

<p>Clearly, $2L \leq C \leq 3L$, since even if there is no overlap, the second shortest path cannot have length less than $L$ and in the worst case, we can pick two times the same path, which maximizes overlap.</p>

<p><strike>This simple algorithm should solve your problem:</p>

<ol>
<li>Calculate the shortest path using your favourite algorithm.</li>
<li><a href="https://en.wikipedia.org/wiki/Homeomorphism_(graph_theory)#Subdivision_and_smoothing" rel="nofollow">Subdivide</a> all edges on the shortest path.</li>
<li>Run your algorithm again on the new graph $G'$ and obtain a second path.</li>
<li>Output the path from 1 and 3 as output, taking care to replace any subdivided edge in it with the original edge.</li>
</ol>

<p>The running time is asymptotically the same for the usual algorithms,since  $G'$ has at most $|E|+|V|$ edges and $|V|$ nodes and $|E|$ is almost always the dominating term of the runtime. This can be ignored however to always have the same running time (see below).</p>

<p>Correctness lies on the correctness of the original algorithm, as well as the fact that by subdividing we minimize according to the quantity $ |P_{2}| + |P_{1} \cap P_{2}| $, as desired.</p>

<p>Finally, note that most algorithms may work with weights from $\mathbb{N}$ with no additional cost, so instead of subdividing one may simply double the weight of the edges along the shortest path. This method is more general and shows that the algorithm works equally well on weighted variants of the problem.</strike></p>

<p>Note that it is not necessary for the shortest path to be part of the optimal solution. See the comments for a discussion on this and thus why my proposed algorithm does not guarantee optimality.</p>

CC BY-SA 3.0
2015-07-20T00:42:23.303Z
Why is it optimal to choose the shortest path as $P_1$? It seems plausible that a different choice of $P_1$ makes it possible to make $|P_1| + |P_2| + |P_1 \cap P_2|$ smaller.
Sasho Nikolov
CC BY-SA 3.0
2015-07-20T07:51:36.913Z
Here is a concrete counter-example along the lines proposed by Sasho Nikolov: The graph contains vertices s, x, y, and t, and five paths between these vertices. There  are 2-edge paths s-x and y-t, 4-edge paths s-y and x-t, and a 1-edge x-y. The two paths should connect s to t. The optimal solution has two disjoint paths s-x-t and s-y-t of cost 6+6=12. The solution found by the above algorithm uses s-x-y-t of cost 5 and another path with total cost at least 13.
Gamow
CC BY-SA 3.0
2015-07-20T07:58:05.840Z
You are correct, it is possible, I mistakenly assumed that the shortest path should always be one of the two. Basically, it suffices to satisfy the condition $|P \cap P_{1}| > |P_{1} \cap P_{2}| + |P_{2}| - |P|$, where $P_{1},P_{2}$ is the optimal solution, $P$ is the shortest path and wlog $|P \cap P_{1}| \leq |P \cap P_{2}|$, which one can easily satisfy with an "artificial" graph of paths. I will edit my answer.
chazisop
CC BY-SA 3.0
2015-07-19T17:04:13.563Z
2015-07-20T08:01:23.657Z
2015-07-20T08:01:23.657Z
chazisop
<p>If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.</p>

<p>The algorithm for shortest pair edge disjoint paths is known as Suurballe's algorithm.</p>

<p><a href="https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm" rel="nofollow">https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm</a></p>

<p>If the cost is some arbitrary function the problem can be NP-complete. 
e.g assuming edge weights one, let the cost function be as $|P_1| + |P_2| + |P_1∩P_2| + 2\cdot |G-P_1\cup P_2|$.
Then the cost is always $ \ge |G|+2$ (if source and terminal are distinct vertices). The equality holds iff the graph has a Hamiltonian cycle.</p>

CC BY-SA 3.0
2015-07-20T19:09:22.773Z
2015-07-23T09:05:10.010Z
2015-07-23T09:05:10.010Z
Saeed
<p>The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.</p>

<p>Consider the following variant:</p>

<p>Find the two shortest paths between 2 pairs of arbitrary nodes, however  the cost is considered to be the length of the path and <em>in addition</em> the number of nearby/common edges in the two paths. This cost is $|P_1| + |P_2| + |P_1 \cap P_2|$ when considering only common edges. More generally we can state the cost as $|P_1| + |P_2| + f(P_1, P_2)$ where it can generalize to consider both penalizing common edges or nearby edges.</p>

<p>Has this problem been addressed before?</p>

CC BY-SA 3.0
2015-07-19T04:17:20.807Z
The objective is not clear to me. Is the cost equal to the weight of the first plus the weight of the second path (so each common edge is counted twice) or is each common edge counted with higher weight, or something else?
Sasho Nikolov
CC BY-SA 3.0
2015-07-20T15:11:32.550Z
It's probably fair to assume @chazisop's interpretation of the question, since the solution to the problem with objective function $|P_1| + |P_2|$ is trivial (take the shortest path twice).
Sasho Nikolov
CC BY-SA 3.0
2015-07-20T19:27:11.877Z
@SashoNikolov The simplest cost is equal to each path cost plus their intersection $|P_1| + |P_2| + |P_1 \cap P_2|$ or more generally  $|P_1| + |P_2| + f(P_1, P_2)$
Otto Nahmee
CC BY-SA 3.0
2015-07-21T06:33:41.250Z
Please edit the question to incorporate that in the question -- don't just leave clarifications in the comments.  The question should stand on its own; people shouldn't have to read the comments.  Are you assuming that every edge has length 1?
D.W.
<graph-theory><optimization><shortest-path>
Finding the two shortest paths while minimizing the number of nearby/common edges
Otto Nahmee
# Finding the two shortest paths while minimizing the number of nearby/common edges

(Asked by: username_0 on 2015-07-19)

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however the cost is considered to be the length of the path and *in addition* the number of nearby/common edges in the two paths. This cost is $|P\_1| + |P\_2| + |P\_1 \cap P\_2|$ when considering only common edges. More generally we can state the cost as $|P\_1| + |P\_2| + f(P\_1, P\_2)$ where it can generalize to consider both penalizing common edges or nearby edges.

Has this problem been addressed before?

**Tags:** graph-theory, optimization, shortest-path
> **Comments:**
> **username_1**: The objective is not clear to me. Is the cost equal to the weight of the first plus the weight of the second path (so each common edge is counted twice) or is each common edge counted with higher weight, or something else?  
> **username_1**: It's probably fair to assume @chazisop's interpretation of the question, since the solution to the problem with objective function $|P_1| + |P_2|$ is trivial (take the shortest path twice).  
> **username_0**: @SashoNikolov The simplest cost is equal to each path cost plus their intersection $|P_1| + |P_2| + |P_1 \cap P_2|$ or more generally  $|P_1| + |P_2| + f(P_1, P_2)$  
> **username_2**: Please edit the question to incorporate that in the question -- don't just leave clarifications in the comments.  The question should stand on its own; people shouldn't have to read the comments.  Are you assuming that every edge has length 1?  

---

## 2 answers

### Answer by username_5 on 2015-07-20. Score: 7 | Accepted answer

If the cost is $|P\_1|+|P\_2|+|P\_1∩P\_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.

The algorithm for shortest pair edge disjoint paths is known as Suurballe's algorithm.

<https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm>

If the cost is some arbitrary function the problem can be NP-complete.
e.g assuming edge weights one, let the cost function be as $|P\_1| + |P\_2| + |P\_1∩P\_2| + 2\cdot |G-P\_1\cup P\_2|$.
Then the cost is always $ \ge |G|+2$ (if source and terminal are distinct vertices). The equality holds iff the graph has a Hamiltonian cycle.


---

### Answer by username_3 on 2015-07-19. Score: -1

Let $P\_{1}$, $P\_{2}$ be two paths in a undirected unweighted graph $G=(V,E)$. We want to minimize the following quantity:

$ C = min\_{P\_{1},P\_{2} \; paths \; in \; G} \{ |P\_{1}| + |P\_{2}| + |P\_{1} \cap P\_{2}| \}$.

Also suppose $L$ is the length of the shortest path in $G$, i.e. $L = min\_{P \; path \; in \; G} \{ |P| \}$

Clearly, $2L \leq C \leq 3L$, since even if there is no overlap, the second shortest path cannot have length less than $L$ and in the worst case, we can pick two times the same path, which maximizes overlap.

This simple algorithm should solve your problem:

1. Calculate the shortest path using your favourite algorithm.
2. [Subdivide](https://en.wikipedia.org/wiki/Homeomorphism_(graph_theory)#Subdivision_and_smoothing) all edges on the shortest path.
3. Run your algorithm again on the new graph $G'$ and obtain a second path.
4. Output the path from 1 and 3 as output, taking care to replace any subdivided edge in it with the original edge.

The running time is asymptotically the same for the usual algorithms,since $G'$ has at most $|E|+|V|$ edges and $|V|$ nodes and $|E|$ is almost always the dominating term of the runtime. This can be ignored however to always have the same running time (see below).

Correctness lies on the correctness of the original algorithm, as well as the fact that by subdividing we minimize according to the quantity $ |P\_{2}| + |P\_{1} \cap P\_{2}| $, as desired.

Finally, note that most algorithms may work with weights from $\mathbb{N}$ with no additional cost, so instead of subdividing one may simply double the weight of the edges along the shortest path. This method is more general and shows that the algorithm works equally well on weighted variants of the problem.

Note that it is not necessary for the shortest path to be part of the optimal solution. See the comments for a discussion on this and thus why my proposed algorithm does not guarantee optimality.

> **Comments:**
> **username_1**: Why is it optimal to choose the shortest path as $P_1$? It seems plausible that a different choice of $P_1$ makes it possible to make $|P_1| + |P_2| + |P_1 \cap P_2|$ smaller.  
> **username_4**: Here is a concrete counter-example along the lines proposed by Sasho Nikolov: The graph contains vertices s, x, y, and t, and five paths between these vertices. There  are 2-edge paths s-x and y-t, 4-edge paths s-y and x-t, and a 1-edge x-y. The two paths should connect s to t. The optimal solution has two disjoint paths s-x-t and s-y-t of cost 6+6=12. The solution found by the above algorithm uses s-x-y-t of cost 5 and another path with total cost at least 13.  
> **username_3**: You are correct, it is possible, I mistakenly assumed that the shortest path should always be one of the two. Basically, it suffices to satisfy the condition $|P \cap P_{1}| > |P_{1} \cap P_{2}| + |P_{2}| - |P|$, where $P_{1},P_{2}$ is the optimal solution, $P$ is the shortest path and wlog $|P \cap P_{1}| \leq |P \cap P_{2}|$, which one can easily satisfy with an "artificial" graph of paths. I will edit my answer.  

---

