title: How to print the path traversed in this Dijkstra's algo?
body: <p>I am not able to print the path traversed using Dijkstra's algorithm. I am getting the right shortest path cost but not able to print the path or nodes that are being traversed for the shortest path.</p>
  
  <pre><code>import java.util.HashSet;
  import java.util.InputMismatchException;
  import java.util.Iterator;
  import java.util.Scanner;
  import java.util.Set;
  
  public class DijkstraAlgorithmSet
  {
  private int distances[];
  private Set&lt;Integer&gt; settled;
  private Set&lt;Integer&gt; unsettled;
  private int number_of_nodes;
  private int adjacencyMatrix[][];
  
  public DijkstraAlgorithmSet(int number_of_nodes)
     {
      this.number_of_nodes = number_of_nodes;
      distances = new int[number_of_nodes + 1];
      settled = new HashSet&lt;Integer&gt;();
      unsettled = new HashSet&lt;Integer&gt;();
      adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
  }
  
  public void dijkstra_algorithm(int adjacency_matrix[][], int source)
  {
      int evaluationNode;
      for (int i = 1; i &lt;= number_of_nodes; i++)
          for (int j = 1; j &lt;= number_of_nodes; j++)
              adjacencyMatrix[i][j] = adjacency_matrix[i][j];
  
      for (int i = 1; i &lt;= number_of_nodes; i++)
      {
          distances[i] = Integer.MAX_VALUE;
      }
  
      unsettled.add(source);
      distances[source] = 0;      
      while (!unsettled.isEmpty())
      {
          evaluationNode = getNodeWithMinimumDistanceFromUnsettled();
          unsettled.remove(evaluationNode);
          settled.add(evaluationNode);
          evaluateNeighbours(evaluationNode);
      } 
  }
  
  private int getNodeWithMinimumDistanceFromUnsettled()
  {
      int min ;
      int node = 0;
  
      Iterator&lt;Integer&gt; iterator = unsettled.iterator();
      node = iterator.next();
      min = distances[node];
      for (int i = 1; i &lt;= distances.length; i++)
      {
          if (unsettled.contains(i))
          {
              if (distances[i] &lt;= min)
              {
                  min = distances[i];
                  node = i;           
              }
          }
      }
      return node;
  }
  
  private void evaluateNeighbours(int evaluationNode)
  {
      int edgeDistance = -1;
      int newDistance = -1;
  
      for (int destinationNode = 1; destinationNode &lt;= number_of_nodes;          destinationNode++)
      {
          if (!settled.contains(destinationNode))
          {
              if (adjacencyMatrix[evaluationNode][destinationNode] !=   Integer.MAX_VALUE)
              {
                  edgeDistance = adjacencyMatrix[evaluationNode]  [destinationNode];
                  newDistance = distances[evaluationNode] + edgeDistance;
                  if (newDistance &lt; distances[destinationNode])
                  {
                      distances[destinationNode] = newDistance;
                  }
                  unsettled.add(destinationNode);
              }
          }
      }
  }
  
  public static void main(String... arg)
  {
      int adjacency_matrix[][];
      int number_of_vertices;
      int source = 0;
      Scanner scan = new Scanner(System.in);
      try
      {
          System.out.println("Enter the number of vertices");
          number_of_vertices = scan.nextInt();
          adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
  
          System.out.println("Enter the Weighted Matrix for the graph");
          for (int i = 1; i &lt;= number_of_vertices; i++)
          {
              for (int j = 1; j &lt;= number_of_vertices; j++)
              {
                  adjacency_matrix[i][j] = scan.nextInt();
                  if (i == j)
                  {
                      adjacency_matrix[i][j] = 0;
                      continue;
                  }
                  if (adjacency_matrix[i][j] == 0)
                  {
                      adjacency_matrix[i][j] =  Integer.MAX_VALUE;
                  }
              } 
          } 
  
          System.out.println("Enter the source ");
          source = scan.nextInt();
  
          DijkstraAlgorithmSet dijkstrasAlgorithm = new DijkstraAlgorithmSet(number_of_vertices);
          dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);
  
          System.out.println("The Shorted Path to all nodes are ");
          for (int i = 1; i &lt;= dijkstrasAlgorithm.distances.length - 1; i++)
          {
              System.out.println(source + " to " + i + " is "+ dijkstrasAlgorithm.distances[i]);
          }
      } catch (InputMismatchException inputMismatch)
      {
          System.out.println("Wrong Input Format");
      }
      scan.close();
     }
  }
  </code></pre>