I am trying to find shortest path between 2 nodes in a graph similar to below:
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!