-2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Are you familiar with Dijkstra's shortest-path algorithm? $\endgroup$ – Shaull May 26 '13 at 7:56
  • $\begingroup$ Yesh Shaull, but im not sure on how to force it to go through a specific node $\endgroup$ – Clar0000 May 26 '13 at 8:25
  • $\begingroup$ 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)? $\endgroup$ – András Salamon May 26 '13 at 8:44
  • $\begingroup$ NO @AndrásSalamon ... or is that a trick question im not getting? $\endgroup$ – Clar0000 May 26 '13 at 9:30
  • 2
    $\begingroup$ 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. $\endgroup$ – jmite May 27 '13 at 14:24
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael May 28 '13 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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