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:
- Calculate the shortest path using your favourite algorithm.
- Subdivide all edges on the shortest path.
- Run your algorithm again on the new graph $G'$ and obtain a second path.
- 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.