This problem related to retail industry. Retail company XYZ have some number of stores. It is providing website for its users, By using this site, users can select items and pickup them from store itself. Here the website makers has to provide shortest path to collect items from the store.

Observe the below Store Map

  1. Blue Node is Starting node (Point where user starts)
  2. Green Node is End node (Point of billing)
  3. Black Nodes are intermediate nodes
  4. Red Nodes are points of item

Basic Algorithm

  1. The basic algorithm is so simple.
  2. Start from starting point, connect next shortest Red node
  3. Connect next unvisited shortest red node from current red node
  4. Connect Green node from current red node

Depth of this algorithm

Now we will go in depth of this algorithm. How will we find shortest red node ?. Here we have to use intermediate nodes (black nodes) with dijkstras algorithm to find shortest distance (Creating Minumum Spanning Tree).  
  1. Find nearest node by dijkstras algorithm from starting node. Now customer will go from starting node to that nearest node and will pick his item.
  2. Then find nearest node from the node where customer picked the item. This node must be other than customer visited item node. Now customer will go from starting node to that nearest node and will pick his item.
  3. Complete 2nd step until customer collects all items.
  4. Then find nearest route from the current item node to target node. Now customer will go through that route and will reach to target billing node

Java Code

Node.java
import java.util.ArrayList;

public class Node implements Comparable<Node>{
    double x;
    double y;
    boolean isVisited;
    boolean isTarget;
    boolean isSource;
    boolean isMainNode;
    ArrayList<Edge> edges = new ArrayList<Edge>();
    double tDist = -1;
    int val;
    ArrayList<Edge> connectingEdges = new ArrayList<Edge>();
    
    public Node(int i, double x, double y, boolean isVisited, boolean isTarget, boolean isSource, boolean isMainNode) {
        this.val = i;
        this.x = x;
        this.y = y;
        this.isVisited = isVisited;
        this.isTarget = isTarget;
        this.isSource = isSource;
        this.isMainNode = isMainNode;
    }
    
    public double getX() {
        return x;
    }
    public void setX(double x) {
        this.x = x;
    }
    public double getY() {
        return y;
    }
    public void setY(double y) {
        this.y = y;
    }
    public boolean isVisited() {
        return isVisited;
    }
    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }
    public boolean isTarget() {
        return isTarget;
    }
    public void setTarget(boolean isTarget) {
        this.isTarget = isTarget;
    }
    public boolean isSource() {
        return isSource;
    }
    public void setSource(boolean isSource) {
        this.isSource = isSource;
    }
    public void addEdge(Edge ed) {
        edges.add(ed);
    }
    public void addConnectingEdge(Edge ed) {
        connectingEdges.add(ed);
    }
    
    
    @Override
    public String toString() {
        return "Node "+val;
    }

    @Override
    public int compareTo(Node o) {
        if(o.val ==  this.val) {
            return 0;
        } else {
            return 1;
        }
    }

    public void addConnectingEdge(ArrayList<Edge> connectignEdges2) {
        connectingEdges.addAll(connectignEdges2);
    }
}
Edge.java
public class Edge {
    Node nd1;
    Node nd2;
    double distance;

    public Edge(Node nd1, Node nd2) {
        this.nd1 = nd1;
        this.nd2 = nd2;
        double xsq = (nd1.x - nd2.x) * (nd1.x - nd2.x);
        double ysq = (nd1.y - nd2.y) * (nd1.y - nd2.y);
        distance = Math.sqrt(xsq + ysq);
        nd1.addEdge(this);
        nd2.addEdge(this);
    }

    public Node getNd1() {
        return nd1;
    }

    public void setNd1(Node nd1) {
        this.nd1 = nd1;
    }

    public Node getNd2() {
        return nd2;
    }

    public void setNd2(Node nd2) {
        this.nd2 = nd2;
    }

    public double getDistance() {
        return distance;
    }

    public void setDistance(double distance) {
        this.distance = distance;
    }

    @Override
    public String toString() {
        return "Edge["+nd1.val+", "+nd2.val+"]";
    }

}

GreedyPath.java
import java.util.ArrayList;

public class GreedyPath {
   
   public static void main(String[] args) {
      Node nd1 = new Node(1, 15, 15, false, false, false, false);
      Node nd2 = new Node(2, 35, 15, false, false, true, false);
      Node nd3 = new Node(3, 55, 15, false, false, false, false);
      
      Node nd4 = new Node(4, 15, 75, false, false, false, false);
      Node trg = new Node(5, 35, 75, false, true, false, false);
      Node nd6 = new Node(6, 55, 75, false, false, false, false);
      
      Node mn1 = new Node(7, 15, 60, false, false, false, true);
      Node mn2 = new Node(8, 35, 45, false, true, false, true);
      Node mn3 = new Node(9, 55, 25, false, false, false, true);
      
      ArrayList<Node> aln = new ArrayList<Node>();
      aln.add(nd1);
      aln.add(nd2);
      aln.add(nd3);
      aln.add(nd4);
      aln.add(trg);
      aln.add(nd6);
      aln.add(mn1);
      aln.add(mn2);
      aln.add(mn3);
      
      new Edge(nd1,nd2);
      new Edge(nd2, nd3);
      new Edge(nd4, trg);
      new Edge(trg, nd6);
      
      new Edge(nd1,mn1);
      new Edge(nd4, mn1);
      new Edge(nd2, mn2);
      new Edge(trg, mn2);
      new Edge(nd3, mn3);
      new Edge(nd6, mn3);
      
      ArrayList<Node> mainPathNodes = new  ArrayList<Node>();
      ArrayList<Edge> mainPathEdges = new  ArrayList<Edge>();
      Node src = nd2;
      mainPathNodes.add(src);
      while(true) {
          resetNodes(aln);
          ArrayList<Node> connected = new  ArrayList<Node>();
          createMinimumSpanningTree(src, aln, connected, 0);
          
          Node minMainNode = null;
          double minDist = Double.MAX_VALUE;
          for(Node nd:connected) {
              if((nd.isMainNode && minDist > nd.tDist) && !mainPathNodes.contains(nd) && nd.val != src.val) {
                  minMainNode = nd;
                  minDist = nd.tDist;
              }
          }
          
          if(minMainNode!=null) {
              mainPathNodes.add(minMainNode);
              mainPathEdges.addAll(minMainNode.connectingEdges);  
              src = minMainNode;
          } else {
              mainPathNodes.add(trg);
              mainPathEdges.addAll(trg.connectingEdges);
              break;
          }
          
      }
      
      System.out.println(mainPathNodes);
      System.out.println(mainPathEdges);
   }
   
   public static void createMinimumSpanningTree(Node src, ArrayList<Node> nodes, ArrayList<Node> connected, double dist) {
       src.tDist = dist;
       src.setVisited(true);
       connected.add(src);
       
       Node minNode = null;
       Node supMinNode = null;
       double minDist = Double.MAX_VALUE;
       Edge minEdge = null;
       for(Node nd:connected) {
           for(Edge ed:nd.edges) {
               if(nd.val == ed.nd1.val) {
                   if(!ed.nd2.isVisited) {
                       double tDist = nd.tDist + ed.distance;
                       if(tDist < minDist) {
                           minDist = tDist;
                           minNode = ed.nd2;
                           minEdge = ed;
                           supMinNode = ed.nd1;
                       }
                   }
               } else {
                   if(!ed.nd1.isVisited) {
                       double tDist = nd.tDist + ed.distance;
                       if(tDist < minDist) {
                           minDist = tDist;
                           minNode = ed.nd1;
                           minEdge = ed;
                           supMinNode = ed.nd2;
                       }
                   }
               }
           }
       }
       
       if(minNode != null) {
           minNode.addConnectingEdge(supMinNode.connectingEdges);
           minNode.addConnectingEdge(minEdge);
           createMinimumSpanningTree(minNode, nodes, connected, minDist);
       }
   }
   
   public static void resetNodes(ArrayList<Node> aln) {
       for(Node nd:aln) {
           nd.setVisited(false);
           nd.tDist = Double.MAX_VALUE;
           nd.connectingEdges.clear();
       }
   }
   
}

50 comments:

  1. very interesting algorithm to learn more about it you can buy coursework on our website and the authors professionals will help you

    ReplyDelete
  2. really sweet algorithm. i will use it on youtube video downloader that is for sure

    ReplyDelete
  3. Thanks for this article very helpful. thanks. know more

    ReplyDelete
  4. Are you searching for cheap assignment writers? We are the best solution for you.
    https://www.cheapassignmentwriters.com/help-with-my-assignment

    ReplyDelete
  5. I love this. It is soo informative. Are you also searching for cheap assignment writing help we are the best solution for you. We are best known for delivering the best services to students without having to break the bank

    ReplyDelete
  6. Thankful to you, I should say to it's adequate post for blog. McDVOICE Survey

    ReplyDelete
  7. Incredible Article. Thankful to you, amazingly obliging.. does coconut flour expire

    ReplyDelete
  8. Ever thought of flaunting a tanned look during winter? Reputable Salon in Boca Raton. If you are under the impression that this could only be possible after. Tanning Salons

    ReplyDelete
  9. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. offshore outsourcing

    ReplyDelete
  10. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. disability concerns

    ReplyDelete
  11. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. boaz derra

    ReplyDelete
  12. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. physicians Disability insurance

    ReplyDelete
  13. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. drug detox in Florida

    ReplyDelete
  14. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. Bitcoin ATM near me

    ReplyDelete
  15. Great weblog here! Additionally your web site loads up fast!
    hyperlink for your host? I want my web site loaded up as fast as yours lol.
    Shalom Lamm

    ReplyDelete
  16. I really like the knowledge you provide here and can't wait to take a look when I get home.

    I'm shocked at how quick your blog loaded on my mobile .. I'm not even using WIFI, just 3G ..

    Anyways, very good blog!
    Shalom Lamm

    ReplyDelete
  17. We will try to hold our overview up to date with brands that do accept players.
    Shalom Lamm

    ReplyDelete
  18. Thank you for the good writeup. It in fact was a amusement account it.

    Look advanced to far added agreeable from you! By the way, how could we communicate?
    Shalom Lamm

    ReplyDelete
  19. Oxycodone is used to cure moderate and severe pain and it can be taken for short term as well as long term. These medicines help to decrease your pain and it sends a message to your brain and after taking it you feel good. If you want to know more or want to Buy Oxycodone Online At Cheapest Rate, then you can check the link below.

    Check it out:- Buy Oxycodone Online At Cheapest Rate

    Contact us:- https://pharmacyorderonline.com/contact-us/

    ReplyDelete
  20. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. AA Meetings Locator

    ReplyDelete
  21. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. Business Capital Loans

    ReplyDelete
  22. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. halfway houses near me

    ReplyDelete
  23. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. CBD Products

    ReplyDelete
  24. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. wholesale CBD supplements

    ReplyDelete
  25. The article was up to the point and described the information about education and learning. Thanks to blog author for wonderful and informative post. Alternative Supplements Blog

    ReplyDelete
  26. wonderfull and informative blog post really very helpfull.
    https://vocal.media/01/richart-ruddie-annuity-views-on-importance-of-digital-marketing

    ReplyDelete
  27. every point in the article is described well i appreciate your work thanku.
    https://theblogulator.com/richart-ruddie-annuity-reviews-on-a-telemarketing-agency/

    ReplyDelete
  28. i like you blog and find it informative about student point of view.
    https://sketchfab.com/Richart.Ruddie.Annuity

    ReplyDelete
  29. Your creative potential seems limitless.
    https://keyposting.com/simplest-ecommerce-website-builder-richart-ruddie-annuity/

    ReplyDelete
  30. You're always learning new things and trying to better yourself. That's awesome.
    https://www.dorjblog.com/richart-ruddie-annuity-describes-telemarketings-pros-and-cons/

    ReplyDelete
  31. I commend you for your thorough work. good working
    https://postpear.com/e-commerce-web-site-builder-by-richart-ruddie-annuity/

    patch.com

    ReplyDelete
  32. A well-developed theme!
    https://vocal.media/01/richart-ruddie-annuity-views-on-importance-of-digital-marketing

    ReplyDelete
  33. Bpautosparesindia.com - Complete Online Tata Spare Parts Catalog, tata auto spare parts shopping India

    ReplyDelete
  34. Choose a Best Website Designing Company In Delhi, which has a diverse portfolio with a variety of projects. Communicate with the vendors so that they know exactly what is expected of them and if possible, invest in buying a package with multiple revision options. Now that you know all about these factors, we hope you would be able to make a wise decision and develop a useful website. This would show you the kind of work they have undertaken in the past and if similar development would be suitable for your business.

    ReplyDelete
  35. But the furious and fast pace at which technology grew brought about a sea-change in the very perspective of website design and development. Website Developers

    ReplyDelete
  36. Thank you so much for this!!! I am currently in school to get my degree for Early Childhood Education and I absolutely LOVE this idea! Thank you so much for the inspiration!

    야동
    대딸방
    스포츠마사지
    출장마사지
    바카라사이트

    ReplyDelete
  37. Maintenance of website performance and uptime 24*7 is certainly impossible for an individual, this is where the monitoring tools come into play. hoepli it

    ReplyDelete
  38. Only aspire to mention ones content can be as incredible. This clarity with your post is superb and that i may think you’re a guru for this issue. High-quality along with your concur permit me to to seize your current give to keep modified by using approaching blog post. Thanks a lot hundreds of along with you should go on the pleasurable get the job done. 바카라사이트

    ReplyDelete
  39. I went over this internet site and I think you have a lot of great info , saved to favorites. 토토사이트


    ReplyDelete
  40. If your car uses more warm-up time, your engine is failing, and that marks the time to order your infallible Suzuki Engine Parts from BP Auto Spares India.

    Suzuki Electrical Parts: Your Suzuki car’s electrical system comprises of the alternator, battery, and the starter. Before you go on long-distance trips, check their health and get the right replacements.

    If your Suzuki car isn’t performing great as in its initial stages, attend to it immediately. Get replacement Suzuki Brake Parts for all your Suzuki brands and drive safely.

    Rejuvenate the look and feel of your Suzuki car with top-notch Suzuki Body Parts. Get custom parts to suit the requirements of individual Suzuki brands.

    ReplyDelete
  41. If you are unable to halt your car without killing the engine, your Suzuki Clutch Parts have become damaged. Order your replacements now and save your Suzuki car.

    Suzuki Suspension Parts tend to wear out with time. But don't wait for complete damage. Restore ride quality and smoothen all ride bumps with our spare parts.

    Genuine and robust Suzuki Gear Parts for all Suzuki cars . Check out our vast list of Suzuki Spare Parts and aftermarket replacement parts here at BP Auto Spares India.

    Get the smooth driving feel of your Suzuki car as when it was new. Make every turn smooth with BP Auto Spares India tried and trusted Suzuki Steering Parts.

    Suzuki Propeller Shaft Parts: When your Suzuki car’s propeller shaft fails, it can detriment the propulsion function capacity. So, be on the alert for steel-to-steel contact, and get your spares always ready.

    Genuine and robust Suzuki Various Pipes and Hoses for all Suzuki cars . Check out our vast list of Suzuki Spare Parts and aftermarket replacement parts here at BP Auto Spares India.

    Genuine and robust Suzuki Other Parts for all Suzuki cars . Check out our vast list of Suzuki Spare Parts and aftermarket replacement parts here at BP Auto Spares India.

    ReplyDelete
  42. This comment has been removed by the author.

    ReplyDelete
  43. This is really interesting, You are a very skilled blogger. I’ve joined your feed and look forward to seeking more of your fantastic post. 바카라사이트

    ReplyDelete
  44. It’s truly a nice and helpful piece of information. I’m happy that you simply shared this helpful information with us. 슬롯머신

    ReplyDelete
  45. We stumbled over here from a different web address and thought I should check things out. 바둑이사이트

    ReplyDelete
  46. Though many aspects of website design differ from site to site, many things remain the same throughout the majority of websites on the internet. Most notably is the navigation or menu. The way in which a website's menu works and looks is very important, as ultimately, visitors to a website are looking for certain criteria that will make them either stay and interact or leave. web design dubai

    ReplyDelete

Blogroll

Popular Posts