0
$\begingroup$

I am trying to find shortest path between 2 nodes in a graph similar to below:

Graph screenshot

Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right.

I am trying to find shortest path from Start to Stop, subject to a constraint (based on already visited nodes). If a node I1_I4 is part of the shortest path, then I cannot include I2_I4, similarly, if I1_I5 is part of shortest path, then I2_I5 cannot be.

So far, I have tried to modify Dijkstra but I am not getting any optimal solutions. Any ideas? Are there any existing graph algorithms for this? Do you have a Java solution for this?

Edit: A bit more detail: I am trying to generate pairs. There is a cost associated with each pair. I can pair I1 with {I4, I5, I6} or I1_D with {I4, I5, I6}. I can also pair I2 with {I4, I5, I6} or I2_D with {I4, I5, I6}. If I have paired I1 with I4 then I cannot pair I4 with I2. Bear in mind that I could pair I1 with I4 but joining I4 with I3 might lead to lower cumulative cost. I am trying to find the minimum cost for these.

Edit2: As depicted in the graph, I can either pair I1 with I4, I5, I6 or I1_D (I1 with a different cost) with I4, I5, I6.

Edit3: I1 and I1_D are mutually exclusive. For instance, I can only choose between I1 and I1_D to pair with I4,I5,I6. In other words, if I1 is a part of any matching pair, I1_D cannot be included in any pairs.

thanks!

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ How extensive can these constraints be? Could there be more columns (e.g. I3_I4, I3_I5, I3_I6), and visiting I1_I4 forbids visiting not only I2_I4 but also I3_I4? If there can be an arbitrary number of such columns, the problem is certainly NP-hard, as it is fairly easy to embed an instance of 3SAT in a graph in such a way that it has a short path iff the 3SAT instance is satisfiable. $\endgroup$ – j_random_hacker May 22 '18 at 17:13
  • $\begingroup$ Yes! there can be I3_I4, I3_I5 and visiting I1_I4 forbids from I3_I4. I have updated problem description with more detail $\endgroup$ – Roh Codeur May 22 '18 at 17:26
  • 1
    $\begingroup$ I think what you're trying to achieve is known as the assignment problem, or finding a maximum matching in a bipartite graph. It's solvable in polynomial time with the Hungarian algorithm (among others). $\endgroup$ – j_random_hacker May 22 '18 at 17:30
  • 1
    $\begingroup$ Adding to @j_random_hacker 's comment, it seems to me that you are trying to express the assignment problem as a max-flow problem. $\endgroup$ – Discrete lizard♦ May 22 '18 at 17:53
  • $\begingroup$ @j_random_hacker: Thanks for your suggestion. However, it doesnt work where I have to consider mutually exclusive constraints, for instance, I can only choose between I1 and I1_D to pair with I4, I5, I6. Similarly, for other nodes as well. Any suggestions? $\endgroup$ – Roh Codeur May 23 '18 at 7:34

Your Answer

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

Browse other questions tagged or ask your own question.