# Find the weight of the lightest path from u to v

Find the weight of the lightest path from u to v the goes through node a or/and b.

Do you have a suggestion on how it can be done?

• Are you familiar with Dijkstra's shortest-path algorithm? – Shaull May 26 '13 at 7:56
• Yesh Shaull, but im not sure on how to force it to go through a specific node – Clar0000 May 26 '13 at 8:25
• Do the weights satisfy the condition that the path you want is $\max\{A,B\}$ where $A$ is the weight of the shortest path from u to a added to the weight of the shortest path from a to v, and similarly for $B$ (via b)? – András Salamon May 26 '13 at 8:44
• NO @AndrásSalamon ... or is that a trick question im not getting? – Clar0000 May 26 '13 at 9:30
• You say the shortest path through a and/or b. AND and OR mean very different things, and if you want an answer, you're going to have to clarify which one it is. – jmite May 27 '13 at 14:24

Suppose we have a graph $G = (V,E)$ and the source $s$ and target $t$ vertices.

There is a variation of the shortest path problem in which one wants to find a simple path from $s$ to $t$ provided that this path visits a subset of the vertices $P \subseteq V$ and it is has minimum cost. Some call it the $(s - P - t)$-shortest path. When we have $P = V$, this problem becomes the Hamiltonian Path Problem, thus telling us that it is $\mathcal{NP}$-hard in general.

Here are some references:
http://epubs.siam.org/doi/abs/10.1137/1015031
http://or.journal.informs.org/content/14/5/909.short

As jmite commented, the difference between AND and OR in your question is quite important. In the scope of this problem I cited, asking the OR version would imply solving the problem for $P_1 = \{a\}$, then for $P_2 = \{b\}$ and outputting the minimum of the two as the answer. The AND version would be the one using $P_3 = \{a,b\}$, which could be a completely different solution.

I don't actually know if there is some polynomial algorithm for this problem when the number of "mandatory" vertices is constant, but I do have a simple way to get a somewhat good lower bound on the solution value.

For the OR version:

1. calculate the SP from $s$ to $a$ and then from $a$ to $t$
2. calculate the SP from $s$ to $b$ and then from $b$ to $t$
3. output the minimum from the two as a LB

For the AND version:

1. calculate the SP from $s$ to $a$, then from $a$ to $b$ and finally from $b$ to $t$
2. calculate the SP from $s$ to $b$, then from $b$ to $a$ and finally from $a$ to $t$
3. output the minimum from the two as a LB

These bounds might not be tight because the subpaths may overlap and not compose a simple path. If I'm not mistaken, they output the actual solution for DAGs.

Also, notice that if either $a$ or $b$ are leaves ($d(a) = 1$ or $d(b) = 1$), then these bounds may be invalid, but the algorithms could easily be fixed.

• I think the standard argument shows that your solution is optimal; that it does not always yield simple paths is clear, as there is not always a simple path with the required properties. – Raphael May 28 '13 at 6:30