title: Dijkstra's algorithm in Java - Multiple requests/threads
body: <p>I am trying to implement Dijkstra’s algorithm in Java REST webservice, I used  <a href="http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java" rel="nofollow">this</a> link for my help.</p>
  
  <p>In this link, it is creating only one graph and calculating one route successfully. But in my program, I am creating multiple graphs and using different variables as cost for each graph. Then I use ExecutorService (total threads = total number of graphs) to find all paths in parallel. My program is working fine when I call it to test paths.</p>
  
  <p>The problem is, when this algorithm receives multiple requests at the same time, it is returning “Unreached” message in printPath() function for some requests, and returning correct paths for other requests successfully. I tested each path one by one, and it is returning correct path each time without any error. Problem occurs only when webservice receives multiple requests at the same time. Below is my code, I only posted classes structure which I am using, rest of the code is same as in above mentioned link.</p>
  
  <p>This is how I am using ExecutorService to find path:</p>
  
  <pre><code>List&lt;RouteFutureResult&gt; rfutureResult = new ArrayList();
      executorService = Executors.newFixedThreadPool(graphs.size());//number of threads is equal to number of graphs
      for (final Graph g : graphs) {
          CalcRoutes calcRoutes = new CalcRoutes(g, other_parameters);
          Future&lt;String&gt; submit = executorService.submit(calcRoutes);
          rfutureResult.add(new RouteFutureResult(submit));
      }
      executorService.shutdown();
      executorService.awaitTermination(Long.MAX_VALUE, TimeUnit.MINUTES);
      //reading response from future object
      List&lt;String&gt; st = new ArrayList();
      for (RouteFutureResult resQuery : rfutureResult) {
          String path = resQuery.getFuture().get();
          st.add(path);
      }
  </code></pre>
  
  <p>This is my CalcRoutes.java call function:</p>
  
  <pre><code>@Override
  public String call() throws Exception {
      List&lt;Double&gt; djst = new ArrayList();
      g.dijkstra(s);
      List&lt;Double&gt; st = g.printPath(d, djst);
      //other processing and returning results
  }
  </code></pre>
  
  <p>Here is the Graph class which I used from mentioned link:</p>
  
  <pre><code>    class Graph {
      private final Map&lt;Double, Vertex&gt; graph;
      public class Edge {
          public final double v1, v2;
          public final double dist;
      }
      public class Vertex implements Comparable&lt;Vertex&gt; {
          public final double name;
          double gid;
          public double dist = Double.MAX_VALUE;
          public Vertex previous = null;
          public final Map&lt;Vertex, Double&gt; neighbours = new HashMap&lt;&gt;();
          private void printPath(List&lt;Double&gt; st) {
              if (this == this.previous) {
                  st.add(this.name);
              } else if (this.previous == null) {
                  System.out.printf("%s(unreached)", this.name);//this is where I am getting a problem when service receives multiple requests at same time
              } else {
                  this.previous.printPath(st);
                  st.add(this.name);
              }
          }
      }
      public Graph(HashMap&lt;Double, RouteResult&gt; edges) {
      }
      public void dijkstra(double startName) {
          if (!graph.containsKey(startName)) {
              System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
              return;
          }
          final Vertex source = graph.get(startName);
          NavigableSet&lt;Vertex&gt; q = new TreeSet&lt;&gt;();
          for (Vertex v : graph.values()) {
              v.previous = v == source ? source : null;
              v.dist = v == source ? 0 : Double.MAX_VALUE;
              q.add(v);
          }
          dijkstra(q);
      }
      private void dijkstra(final NavigableSet&lt;Vertex&gt; q) {
          Vertex u, v;
          while (!q.isEmpty()) {
          }
      }
      public List&lt;Double&gt; printPath(double endName, List&lt;Double&gt; st) {
          if (!graph.containsKey(endName)) {
              System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
          }
          graph.get(endName).printPath(st);
          return st;
      }
  }
  </code></pre>
  
  <p>This is how I am creating multiple graphs:</p>
  
  <pre><code>Graph cost = new Graph(MRoute); //MRoute is the hashmap
  graphs.add(cost);//graphs is a list containing multiple graphs
  </code></pre>
  
  <p>I also checked already posted questions about Dijkstra's algorithm, but I couldn't find any relevant question to my problem. Somehow, this algorithm is unable to handle multiple requests, please guide me, any help would be highly appreciated.</p>