0

I use JGraphT library to work with a quite complex topology. There is a plenty of library algorithms like Dijkstra Shortest Path provided by the library. My question is: I need a way to find a path via some dedicated vertex, which is not the "shortest" one and even may seem "contra-intuitive" to choose (even though there is a guaranteed path from start to end via this vertex in the graph). For example, let's assume, I can get from New York to Paris directly, but I want to go to Paris by going first to Sidney, then to Tokio, then to Moscow, then to Berlin, then to Paris. So Paris is my goal, but I want to define some specific "intermediate" vertices, which MUST BE on the path. What means are there to achieve this using JGrapthT?

Software Craftsman
  • 2,999
  • 2
  • 31
  • 47
  • Here is an already answered question addressing a similar problem (not specifically related to JGraphT, but to graph theory in general): https://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes Strange enough, I searched for solutions before asking the question, but did not find this, maybe because of JGraphT keyword which I included. – Software Craftsman Apr 28 '20 at 11:02

1 Answers1

1

It is a very interesting question. I don't know of a specific solution but what I would do is just find the shortest path between each set of desired nodes.

So you find the shortest path for

Paris -> Sydney
Sydney -> Tokyo
Tokyo -> Moscow
Moscow -> Berlin
Berlin -> Paris

and then add them together.

Of course that could mean that you pass through one of the desired nodes anyway. I'm not sure how you would want to deal with that situation.

mwarren
  • 759
  • 3
  • 6