java - Dijkstra's algorithm with 'must-pass' nodes -

i trying implement dijkstra's algorithm can find shortest path between start node , end node. before reach end node there 'must-pass' intermediate nodes (more one) example 2 or 3 must pass nodes must pass before reach end node.

if have 1 must pass node solution found find 2 different paths must pass node destination , must pass node start node.

i out of ideas how can implement such algorithm. suggestions?

thanks.

list<node> closestpathfromorigin = null;  double maxd = double.positive_infinity; double _distance = 0; int temp1 = 0; list<node> referencepath = new arraylist<>(); boolean check = false; node startnode = null;  public list<node> recursion(arraylist<node> points, arraylist<node> intermediatepoints) {      if (!check) {         system.out.println("--- data ---");         system.out.println("intermediate points: " + intermediatepoints);         system.out.println("points: " + points.get(0).lat + " " + points.get(1).lat);         system.out.println("--find nearest intermediate point start point of driver--");         startnode = points.get(0);         system.out.println("start point of driver: " + startnode.lat + " " + startnode.lon);         (int = 0; < intermediatepoints.size(); i++) {             list<node> _path = dijkstra(startnode, intermediatepoints.get(i));             _distance = 0;             (int j = 0; j < _path.size() - 1; j++) {                 _distance += calculatedistance(_path.get(j), _path.get(j + 1));             }             if (_distance < maxd) {                 maxd = _distance;                 closestpathfromorigin = _path;                 temp1 = i;             }         }         system.out.println("nearestpoint driver's origin: " + intermediatepoints.get(temp1));          referencepath.addall(closestpathfromorigin);         startnode = intermediatepoints.get(temp1);         system.out.println("new startnode: nearestpoint driver's origin: " + startnode.lat + " " + startnode.lon);         check = true;         intermediatepoints.remove(intermediatepoints.get(temp1));         system.out.println("new intermediate points: " + intermediatepoints);         system.out.println("intermediate points empty? no -> recursion, yes -> stop");         if (!intermediatepoints.isempty()) {             system.out.println("recursion!!! new data of: intermediatepoints: " + intermediatepoints);             recursion(points, intermediatepoints);         } else {             system.out.println("stop");             return referencepath;         }     } else {         system.out.println("recursion: startnode: " + startnode.lat + " " + startnode.lon);         (int = 0; < intermediatepoints.size(); i++) {             if (intermediatepoints.size() > 1) {                 system.out.println("from new start point next nearest intermediate points if more 1 points");                 list<node> _path = dijkstra(startnode, intermediatepoints.get(i));                 _distance = 0;                 (int j = 0; j < _path.size() - 1; j++) {                     _distance += calculatedistance(_path.get(j), _path.get(j + 1));                 }                 if (_distance < maxd) {                     maxd = _distance;                     closestpathfromorigin = _path;                     temp1 = i;                 }                 referencepath.addall(closestpathfromorigin);                 startnode = intermediatepoints.get(temp1);                 check = true;                 intermediatepoints.remove(intermediatepoints.get(temp1));                 if (!intermediatepoints.isempty()) {                     recursion(points, intermediatepoints);                 } else {                     return referencepath;                 }             } else {                 system.out.println("from new start point next nearest intermediate points if 1 point");                 list<node> _path = dijkstra(startnode, intermediatepoints.get(i));                 //collections.reverse(_path);                 referencepath.addall(_path);             }             if (i == intermediatepoints.size() - 1) {                 system.out.println("last entry in intermediate points - find path destination: " + points.get(1).lat + " " + intermediatepoints.get(i));                 //list<node> _path1 = dijkstra(points.get(1), intermediatepoints.get(i));                 list<node> _path1 = dijkstra(intermediatepoints.get(i), points.get(1));                  collections.reverse(_path1);                 referencepath.addall(_path1);                //  referencepath.addall(_path2);             }         }     }     return referencepath; } 

this generalisation of travelling salesman problem. tsp comes case vertices "must-pass".

find shortest paths between each pair of must-pass vertices, source each must-pass vertex, , each must-pass vertex sink. use famous o(n 2^n) dynamic programming algorithm tsp find shortest path source sink meeting constraints; here n 2 plus number of must-pass vertices.