1
$\begingroup$

I have a directed graph with roughly 2000 nodes, and roughly 4000 edges. I have created an application so the people that use it can easily see the path drawn on a map, if they e.g. want to find the shortest path between two nodes. And this works as intended. However, this shortests path is based on the weights of each edge. The "problem", as I have been told, is, that sometimes they (who have done this manually for years) know that this route needs to go through a certain node. There are certain reasons for this, but nonetheless, I need to be able to force a path to go through certain nodes.

My first idea was to just run Dijkstra's from start node to intermediate node and then from intermediate node to end node, and combine the two. And in some cases, this seems to work. But as you can imagine, sometimes the second path might go through some of the edges/nodes that was used in the first path, which doesn't work.

I could probably make some modified node disjoint path work if there was only ONE intermediate node. But I am afraid that it will get quite complicated if I were to use more than that.

So I am wondering if there might be a better option to still get the shortest path, but with forced intermediate nodes in between ?

It should also be noted that computation time is not really an issue here. Nothing needs to be almost instant, and in general it seems that a graph of this magnitude is quite "small" in terms of computation time.

Improve this question
$\endgroup$
4
  • $\begingroup$ So you want a simple (no repeated vertices) shortest path from start to end that traverses an arbitrary set of intermediate nodes (given in input)? $\endgroup$
    – Steven
    Oct 4, 2021 at 12:35
  • 1
    $\begingroup$ The problem is NP-complete in general, but not necessarily so for undirected graphs. It is also known to be FPT for planar graphs. What is better is not easy to say without more information. Do you need exact answers (i.e. the shortest possible paths), or are approximate answers good enough? How many intermediate nodes do you think is necessary? $\endgroup$
    – Pål GD
    Oct 4, 2021 at 13:45
  • $\begingroup$ @Steven, yes no repeated vertices would be the optimal solution. $\endgroup$
    – Denver Dang
    Oct 5, 2021 at 7:36
  • 1
    $\begingroup$ @PålGD, In my case, at least when I don't use node disjoint path algorithms, it is somewhat undirected, i.e. all edges have a counterpart. So it's only when the node disjoint stuff are enabled, that it becomes a true directed graph. $\endgroup$
    – Denver Dang
    Oct 5, 2021 at 8:15

1 Answer 1

Reset to default
2
$\begingroup$

The problem you are trying to solve is $\mathsf{NP}$-Hard. In fact, it is hard to even decide whether any such path exists.*

Indeed, let $G=(V,E)$ be your graph and $s,t \in V$ be the start and end nodes, respectively. When the set of intermediate nodes is $V \setminus \{s,t\}$ the problem is equivalent to finding an Hamiltonian path from $s$ to $t$ in $G$, which is a well-known $\mathsf{NP}$-Hard problem.

* Note that even if you know for sure that the sought path exists in $G$, this still doesn't simplify the problem since you can transform an instance of Hamiltonian-path into an instance of your problem by adding all missing edges and assigning a high cost to them. Then, deciding whether there is an Hamiltoniam path in the original graph corresponds to deciding whether there exists a cheap path from $s$ to $t$ that traverses all vertices in $V \setminus \{s,t\}$ in the modified graph.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Maybe I'm wrong, but how about multiplying the graph to several clones. The movement from one clone to the next-level clone is done only by passing through a vertex from the "must pass" list. Then, we run Dijkstra from $s_0$ to $t_k$, where $k$ is the amount of "must pass" vertices. $\endgroup$
    – Marik S.
    Oct 13, 2021 at 12:06
  • 1
    $\begingroup$ How do you keep track of the already visited vertices? You'll need $2^k$ copies, one for every subset of must-pass vertices. Plus you need to somehow ensure that the corresponding path on the original graph stays simple. $\endgroup$
    – Steven
    Oct 13, 2021 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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