Dijkstra Algorithm Program

import java.io.*;

class DijDemo 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter number of nodes: - ");
      Dijkstra obj = new Dijkstra(Integer.parseInt(br.readLine()));  
   obj.Start(); 
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
  
 }
}

class Dijkstra
{
 private String[] name; //to store names of the vertex
 private int[][] matrix; //to store values of the connections
 private Vertex[] v; //to keep tag values of each vertex

 BufferedReader br;

 Dijkstra(int n)
 {
  name = new String[n];
  matrix = new int[n][n]; 
  v = new Vertex[n];

  try
  {
   br = new BufferedReader(new InputStreamReader(System.in));
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }


 private void initialize() //set the intial tag for each vertex
 {
  for(int i=0; i<v.length; i++)
  {
   v[i] = new Vertex();
   v[i].dist = -1;
   v[i].prev_index = -1;
   v[i].permanent = false;
  }
 }

 private String getName(int index) //of the vertex at a particular index
 {
  return name[index]; 
 }

 private int getIndex(String nm) //of the vertext
 {
  for(int i=0; i<name.length; i++)
   if(name[i].equals(nm))
    return i;
  return -1;
 }

 private void setNames() //of the vertices
 {
  try
  {
   for(int i=0; i<name.length; i++) 
    name[i] = br.readLine();
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }

 private int getStart() //accept the start vertex for the graph
 {
  try
  {
   return getIndex(br.readLine());
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }

  return -1;
 } 

 private void setEdgeDetails() //get connection details
 {
  for(int i=0; i<matrix.length; i++)
  {

   System.out.println("== "  + getName(i) + " ==");

   for(int j=i; j<matrix[i].length; j++)
   {

    if(i==j)
    {
     matrix[i][j] = 0;
     continue;
    }


    try
    {
     System.out.print(getName(j) + ": ");
     matrix[j][i] = matrix[i][j] = Integer.parseInt(br.readLine());
    }
    catch(Exception e)
    {
     e.printStackTrace();
    } 
   }
  }
 }
 
 
 private void dijkstra(int cvx)
 {
  Vertex cur = v[cvx];
  cur.dist=0;
  cur.permanent = true;
  cur.prev_index=-1; 

  

  while(true)
  {
   int[] vertexRow = matrix[cvx];

   System.out.println("For parent node " + getName(cvx));

   for(int j=0; j<vertexRow.length; j++)
   {
    if(vertexRow[j] > 0)
    {
     int newDistance = (cur.dist+vertexRow[j]);
     setTag(j, cvx, newDistance);
    }
   }

   cvx = findNonPermanentVertexWithMinimumDist();

   if(cvx==-1)
    break;

   v[cvx].permanent = true;

   cur = v[cvx];
  }
 }

 private void setTag(int current_vertex, int parent_vertex, int distance)
 {
  Vertex cur = v[current_vertex];

  if(cur.permanent!=true)
  {
   if(cur.dist!=-1 && cur.dist!=0)
   {
     if (cur.dist>distance)
     {
     cur.prev_index = parent_vertex;
     cur.dist = distance;
     }
   }
   else
   {
     cur.prev_index = parent_vertex;
     cur.dist = distance;
   }
   
  }
 }

 private int findNonPermanentVertexWithMinimumDist()
 {  
  int minDist=-1;
  int minIndex=-1;
  int i=0;

  for(; i<v.length; i++)
  {
   if(v[i].permanent==false)
   {
    if(v[i].dist!=-1)
    {
     if(minIndex==-1)  //if the first node encountered then
     {
      minDist=v[i].dist;
      minIndex=i;
     }
     else
     {
      if(v[i].dist<minDist)
      {
       minDist=v[i].dist;
       minIndex=i; 
      }
     }
    }
   }
  }
  
  return minIndex;
 }

 private void showVertexDetails(int i) //vertex details
 {
   System.out.println("Vertex: " + getName(i));
   System.out.println("Distance= " + v[i].dist);
   if(v[i].prev_index!=-1)
   System.out.println("Previous= " + name[v[i].prev_index]);
   System.out.println("Permanent= " + v[i].permanent);
  
 }

 public void Start()
 {
  System.out.println("Enter names of vertices: ");
  setNames();

  System.out.println("Enter wt. for each edge. if edge does not exists (-1)");
  setEdgeDetails();

  initialize();

  System.out.print("Enter name of start vertex - ");

  dijkstra(getStart());

  for(int i=0; i<name.length; i++)
   System.out.println(traversePath(i) + ": " + v[i].dist);

 }

 private String traversePath(int vx)
 {
  StringBuffer path = new StringBuffer(getName(vx) + " - ");

  int prev = v[vx].prev_index;

  while(prev!=-1)
  {
   path.append(getName(prev) + " - ");
   prev=v[prev].prev_index;   
  }

  return path.reverse().toString().substring(2);
 }

}


class Vertex //tag structure
{
 int dist;
 int prev_index;
 boolean permanent;
}

---

Undirected Graph on which Dijkstra Algorithm worked to find the shortest path for each node.

Result of the Dijkstra Algorithm