title: Use Dijkstra's algorithm to get shortest path when distance are as coordinates
body: <p>I had a looked at other posts regarding this here at SO.</p>
  <p>I'm trying to find the shortest path between nodes in a graph. Each edge between nodes has an <code>(X, Y)</code> coordinate.</p>
  <p>I want to calculate the shortest distance from <code>Node I</code> to <code>Node J</code>. Once have that I want to add up all the X values and Y values from the coordinates in shortest path.</p>
  <p>I have been stuck at this for hours and would love some insight.</p>
  <p>Here is the code:</p>
  <pre><code>class Vertex implements Comparable&lt;Vertex&gt; {
      private int id;
      private List&lt;Edge&gt; adjacencyList;
      private Vertex previousVertex;
      private double minDistance;
      private Coordinate point;
      
      public Vertex(int id, Coordinate point) {
          this.id = id;
          this.point = point;
          this.adjacencyList = new ArrayList&lt;&gt;();
      }
      
      public int getID() {
          return this.id;
      }
      
      public Coordinate getPoint() {
          return this.point;
      }
      
      public List&lt;Edge&gt; getAdjacencyList() {
          return this.adjacencyList;
      }
      
      public void addNeighbour(Edge edge) {
          this.adjacencyList.add(edge);
      }
      
      public Vertex getPreviousVertex() {
          return this.previousVertex;
      }
      
      public void setPreviousVertex(Vertex previousVertex) {
          this.previousVertex = previousVertex;
      }
      
      public double getMinDistance() {
          return this.minDistance;
      }
      
      public void setMinDistance(double minDistance) {
          this.minDistance = minDistance;
      }
      
      public int compareTo(Vertex other) {
          return Double.compare(this.minDistance, other.minDistance);
      }
  }
  
  
  class Edge {
      private double weight;
      private Vertex targetVertex;
      
      public Edge(double weight, Vertex targetVertex) {
          this.weight = weight;
          this.targetVertex = targetVertex;
      }
      
      public double getWeight() {
          return this.weight;
      }
      
      public void setWeight(double weight) {
          this.weight = weight;
      }
      
      public Vertex getTargetVertex() {
          return this.targetVertex;
      }
          
      public void setTargetVertex(Vertex targetVertex) {
          this.targetVertex = targetVertex;
      }
  }
  
  class Algorithm {
      public void shortestPath(Vertex startVertex) {
          startVertex.setMinDistance(0);
          PriorityQueue&lt;Vertex&gt; queue = new PriorityQueue&lt;&gt;();
          queue.add(startVertex);
          
          while (!queue.isEmpty()) {
              Vertex actualVertex = queue.poll();
              
              for (Edge edge : actualVertex.getAdjacencyList()) {
                  Vertex v = edge.getTargetVertex();
                  double weight = edge.getWeight();               
                  double currentDistance = actualVertex.getMinDistance() + weight;
                  
                  if (currentDistance &lt; v.getMinDistance()) {
                      queue.remove(v);
                      v.setMinDistance(currentDistance);
                      v.setPreviousVertex(actualVertex);
                      queue.add(v);
                  }
              }
          }
      }
      
      public List&lt;Vertex&gt; getShortestPathTo(Vertex targetVertex){
          List&lt;Vertex&gt; path = new ArrayList&lt;Vertex&gt;();
          for (Vertex vertex = targetVertex; vertex != null; vertex = vertex.getPreviousVertex()){
              path.add(vertex);
          }
          Collections.reverse(path);
          return path;    
      }
  }
  
  class Coordinate {
      private int x;
      private int y;
      
      Coordinate(int x, int y) {
          this.x = x;
          this.y = y;
      }
      
      public int getX() {
          return this.x;
      } 
      
      public int getY() {
          return this.y;
      }
  
      public static Coordinate readInput(Scanner in) {
         String[] temp = in.nextLine().split(&quot; &quot;);
         return new Coordinate(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
      }
  }
  </code></pre>
  <p>If I read from this textfile</p>
  <blockquote>
  <p>3   //# of coordinates</p>
  <p>0 0 // (x, y)</p>
  <p>1 1  // (x, y)</p>
  <p>2 0  // (x, y)</p>
  <p>1 2  //edge between coordinate 1 to 2</p>
  <p>2 3  //edge between coordinate 2 to 3</p>
  </blockquote>
  <p>My test case would look like this:</p>
  <pre><code>class Test {
      public static void main(String[] args) {
          
          Scanner s = new Scanner(System.in);
          String[] constants = s.nextLine().split(&quot; &quot;);
          
          final int N = Integer.parseInt(constants[0]);
          
          List&lt;Coordinate&gt; junctions = new ArrayList&lt;&gt;();
          List&lt;Coordinate&gt; paths = new ArrayList&lt;&gt;();
          List&lt;Vertex&gt; vertices = new ArrayList&lt;&gt;();
          
          for(int i = 0; i &lt; N; i++) {
              junctions.add(Coordinate.readInput(s));
          }
          
          for(int i = 0; i &lt; N-1; i++) {
              paths.add(Coordinate.readInput(s));
          }
          
          for(int i = 0; i &lt; N-1; i++) {
              int x = junctions.get(paths.get(i).getX() - 1).getX();
              int x1 = junctions.get(paths.get(i).getY() - 1).getX();
              int y = junctions.get(paths.get(i).getX() - 1).getY();
              int y1 = junctions.get(paths.get(i).getY() - 1).getY();
                  
              Vertex vertex1 = new Vertex(paths.get(i).getX(), new Coordinate(x, y));
              Vertex vertex2 = new Vertex(paths.get(i).getY(), new Coordinate(x1, y1));
                  
              double distance = Math.sqrt(Math.pow(x - x1, 2) + Math.pow(y - y1, 2));
              
              vertex1.addNeighbour(new Edge(distance, vertex2));
              
              vertices.add(vertex1);
              vertices.add(vertex2);
          }
          
          Algorithm a = new Algorithm();
          int x = 0;
          int y = 0;
          
          for(int i = 0; i &lt; vertices.size(); i++) {
              a.shortestPath(vertices.get(i));
              
              for(Vertex vertex : a.getShortestPathTo(vertices.get(i+1))) {
                  x += vertices.get(vertex.getID()).getPoint().getX();
                  y += vertices.get(vertex.getID()).getPoint().getY();
              }
              
          }
          //This prints out &quot;Total X: 5 Total Y: 3&quot; (should be 3 and 1)
          System.out.println(&quot;Total X: &quot; + x + &quot; Total Y: &quot; + y);
      }
  }
  </code></pre>