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();
       }
   }
   
}

1 comment:

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

    ReplyDelete

Blogroll

Follow this blog by Email

Popular Posts