title: All-Pairs Shortest Paths by Dijkstra
body: <p>I searched for the Java implementation of all-pairs shortest paths by Dijkstra.
  I found an algorithm for one source shortest path. I actually don't know Java, but I'm studying discrete mathematics, so maybe someone can help me. What I have to change to make it an all-pairs shortest path? </p>
  
  <p>----------Edit -------
  thanks templatetypedef again. i try it. now i think there is another little mistake in the code.</p>
  
  <p>The input file(try.txt):</p>
  
  <pre><code> 0 2 68
   3 4 97
   0 3 8
  </code></pre>
  
  <p>This is the wrong output i get:</p>
  
  <pre><code>    From 3:
  Shortest Path Cost to 3 is: 0.0
  Shortest Path Cost to 2 is: Infinity
  Shortest Path Cost to 0 is: Infinity
  Shortest Path Cost to 4 is: 97.0
  
  From 2:
  Shortest Path Cost to 3 is: Infinity
  Shortest Path Cost to 2 is: 0.0
  Shortest Path Cost to 0 is: Infinity
  Shortest Path Cost to 4 is: 97.0
  
  From 0:
  Shortest Path Cost to 3 is: 8.0
  Shortest Path Cost to 2 is: 68.0
  Shortest Path Cost to 0 is: 0.0
  Shortest Path Cost to 4 is: 97.0
  
  From 4:
  Shortest Path Cost to 3 is: 8.0
  Shortest Path Cost to 2 is: 68.0
  Shortest Path Cost to 0 is: Infinity
  Shortest Path Cost to 4 is: 0.0
  </code></pre>
  
  <p>The code: </p>
  
  <pre><code>import java.io.BufferedReader;
  import java.io.FileReader;
  import java.io.IOException;
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.PriorityQueue;
  
  class Vertex implements Comparable&lt;Vertex&gt; {
      public final String name;
      public List&lt;Edge1&gt; adjacencies;
      public double minDistance = Double.POSITIVE_INFINITY;
      public Vertex previous;
  
      public Vertex(String argName) {
          name = argName;
          adjacencies = new ArrayList&lt;Edge1&gt;();
      }
  
      public void addEdge(Edge1 e) {
          adjacencies.add(e);
      }
  
      public String toString() {
          return name;
      }
  
      public int compareTo(Vertex other) {
          return Double.compare(minDistance, other.minDistance);
      }
  
  }
  
  class Edge1{
      public final Vertex target;
      public final double weight;
  
      public Edge1(Vertex argTarget, double argWeight) {
          target = argTarget;
          weight = argWeight;
      }
  }
  
  
  public class Dijkstra {
  
      public static void computePaths(Vertex source) {
          source.minDistance = 0.;
          PriorityQueue&lt;Vertex&gt; vertexQueue = new PriorityQueue&lt;Vertex&gt;();
          vertexQueue.add(source);
  
          while (!vertexQueue.isEmpty()) {
              Vertex u = vertexQueue.poll();
  
              // Visit each Edge exiting u
  
              for (Edge1 e : u.adjacencies) {
                  Vertex v = e.target;
                  double weight = e.weight;
                  double distanceThroughU = u.minDistance + weight;
                  if (distanceThroughU &lt; v.minDistance) {
                      vertexQueue.remove(v);
                      v.minDistance = distanceThroughU;
                      v.previous = u;
                      vertexQueue.add(v);
                  }
  
              }
          }
      }
  
      public static List&lt;Vertex&gt; getShortestPathTo(Vertex target) {
          List&lt;Vertex&gt; path = new ArrayList&lt;Vertex&gt;();
          for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
              path.add(vertex);
  
          Collections.reverse(path);
          return path;
      }
  
      public static void main(String args[]) {
  
          Map&lt;String, Vertex&gt; vertexMap = new HashMap&lt;String, Vertex&gt;();
          BufferedReader in = null;
          try {
              in = new BufferedReader(new FileReader("try.txt"));
              String line;
              boolean inVertex = true;
  
              while ((line = in.readLine()) != null) {
  
  
                      //store the edges
                      String[] parts = line.split(" ");
                      String vFrom = parts[0];
                      String vTo = parts[1];
                      if(!vertexMap.containsKey(vFrom))
                      {
                          Vertex v= new Vertex(vFrom);
                          vertexMap.put(vFrom, v);
                      }
                      if(!vertexMap.containsKey(vTo))
                      {
                          Vertex v1= new Vertex(vTo);
                          vertexMap.put(vTo, v1);
                      }
  
  
                      double weight = Double.parseDouble(parts[2]);
                      Vertex v = vertexMap.get(vFrom);
                      if (v != null) {
                          v.addEdge(new Edge1(vertexMap.get(vTo), weight));
  
                  }
              }
          } catch (IOException e) {
              e.printStackTrace();
              return;
          }
          finally{
              if(in!= null)
                  try {
                      in.close();
                  } catch (IOException ignore) {
                  }
          }
  
          //get a list of all the vertices
          Collection&lt;Vertex&gt; vertices = vertexMap.values();
  
          //Vertex source = vertices.iterator().next();
          for(Vertex source:vertices){
          System.out.println("From " + source+":");
          computePaths(source);
          for (Vertex v : vertices) {
              System.out.println("Shortest Path Cost to " + v + " is: " + v.minDistance);
             // List&lt;Vertex&gt; path = getShortestPathTo(v);
            //  System.out.println("Path: " + path);
          }System.out.println();
          source.minDistance=Double.POSITIVE_INFINITY;
          source.previous=null;}
      }
  }
  </code></pre>