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.


Comments

Post a Comment

Popular posts from this blog

javascript - Jquery show_hide, what to add in order to make the page scroll to the bottom of the hidden field once button is clicked -

i have button on website when clicked, reveals map. button can seen when page first loads up, when clicked, section holding map slides open , goes out of screen since page loads @ top (normal). want page scroll down bottom of div select when button pushed, if map out of screen. if page scrolled down, , clicks show map button, don't want page jump bottom of map. i tried figure out myself, no luck. seasoned jquery coders able give me guidance? many thanks! map = mapdiv.gmap3("get"); infobox = new infobox({ pixeloffset: new google.maps.size(-220, -310), closeboxurl: '', enableeventpropagation: true }); mapdiv.delegate('.infobox .close','click',function () { infobox.close(); }); jquery(".slidingdiv").hide(); jquery(".show_hide").show(); jquery('.show_hide').click(function(){ lastcenter=map.getcenter(); jquery(".slidingdiv...
Read more

python - Django-cities exits with "killed" -

i trying install django-cities on server 500mb ram. whenever run: manage.py cities the system exits saying killed. trying run: manage.py cities --import=country --force worked, guessing matter of running out of memory. to bypass, tried refer package local copy of cities' data file. still didn't work. any ideas on how can migrate data without having increase memory on server? based on suggestion comments, solved setting temporary swap file. if unfamiliar it, can follow these steps: set swap file touch /var/swap.img chmod 600 /var/swap.img set swap file size cd /var dd if=/dev/zero of=/var/swap.img bs=1024k count=1000 this create 1gb swap file. prepare disk image mkswap /var/swap.img activate swap memory swapon /var/swap.img once done, can turn off swap image: swapoff /var/swap.img more information on virtual memory , swap files can found here: https://www.digitalocean.com/community/tutorials/how-to-configure-virtual-me...
Read more

python - How to get a widget position inside it's layout in Kivy? -

i have gridlayout , added image widgets on after adding of images want draw rectangle in each image using canvas couldn't because don't know exact image widgets positions on gridlayout. code: http://paste.ofcode.org/3bdp9yhjrcrzmsztbu9hqp4 http://paste.ofcode.org/3az3gx4fxzr9dlhe2ami97c in last line of python code : rectangle(pos = (child.x - 2.4, child.y + 467), size = (70, 70)) how draw rectangle in child(my method not good^), also why gridlayout not coming in center after setting it's pos_hint = {"center_x" : .5}? if understand question right, try use such methods to_local() , to_parent() , to_widget() , to_window() . try substract position of gridlayout widgets' positions.
Read more