Comparative Study of Array Sorting Techniques

----------------------------------------------------------

Algorithm       |    Comparisons     |    Moves

----------------------------------------------------------

----------------------------------------------------------

DataSet 1: 1    2    3    4    5    6    7    8    9    10  

Insertion Sort  |    45         |    0

Selection Sort  |    45         |    0

Bubble Sort     |    45         |    0

EEBubble Sort   |    9          |    0

Shaker Sort     |    9          |    0

Shell Sort      |    62         |    0

Heap Sort       |    80         |    90

Quick Sort      |    25         |    0

----------------------------------------------------------

DataSet 2: 10   9    8    7    6    5    4    3    2    1   

Insertion Sort  |    9          |    54

Selection Sort  |    45         |    15

Bubble Sort     |    45         |    135

EEBubble Sort   |    45         |    135

Shaker Sort     |    45         |    135

Shell Sort      |    62         |    39

Heap Sort       |    67         |    63

Quick Sort      |    25         |    15

----------------------------------------------------------

DataSet 3: 10   1    2    3    4    5    6    7    8    9   

Insertion Sort  |    45         |    18

Selection Sort  |    45         |    27

Bubble Sort     |    45         |    27

EEBubble Sort   |    17         |    27

Shaker Sort     |    17         |    27

Shell Sort      |    62         |    27

Heap Sort       |    71         |    81

Quick Sort      |    45         |    27

----------------------------------------------------------

DataSet 4: 10   2    3    4    5    6    7    8    9    1   

Insertion Sort  |    37         |    26

Selection Sort  |    45         |    3

Bubble Sort     |    45         |    51

EEBubble Sort   |    45         |    51

Shaker Sort     |    24         |    51

Shell Sort      |    57         |    41

Heap Sort       |    75         |    81

Quick Sort      |    25         |    3

----------------------------------------------------------

DataSet 5: 10   1    3    4    5    6    7    8    9    2   

Insertion Sort  |    38         |    25

Selection Sort  |    45         |    6

Bubble Sort     |    45         |    48

EEBubble Sort   |    45         |    48

Shaker Sort     |    24         |    48

Shell Sort      |    57         |    38

Heap Sort       |    75         |    78

Quick Sort      |    25         |    6

----------------------------------------------------------

DataSet 6: 2    1    4    3    6    5    8    7    10   9   

Insertion Sort  |    45         |    10

Selection Sort  |    45         |    15

Bubble Sort     |    45         |    15

EEBubble Sort   |    17         |    15

Shaker Sort     |    17         |    15

Shell Sort      |    62         |    15

Heap Sort       |    78         |    87

Quick Sort      |    23         |    15

Quick Sort in Java

import java.io.*;

class QuickSortDemo 
{
 static int[] a;
 static int c=0,m=0; //variables to keep track of comparisons and moves

 public static void swap(int x, int y)
 {
  int temp = a[x];
  a[x] = a[y];
  a[y] = temp;
  m+=3;
 }

 public static void quickSort(int lb, int ub)
 {
  if(lb>=ub)
   return;

  int down = lb;
  int up = ub;
  int pivot_index = findPivotIndex(lb,ub);

  while(down<up)
  {   
   while(a[down]<=a[pivot_index] && down<up)
   {
    c++;
    down++;
   }
   
   while(a[up]>a[pivot_index])
   {
    c++;
    up--;
   }

   if(down<up)
    swap(down,up);
  }

  if(pivot_index!=up)
   swap(pivot_index,up);

  quickSort(lb,up-1);
  quickSort(up+1,ub);
 }

 public static int findPivotIndex(int lb, int ub)
 {
  int x1=a[lb];
  int x2=a[(lb+ub)/2];
  int x3=a[ub];

  if(x1>x2 && x1<x3 || x1<x2 && x1>x3)
   return lb;

  if(x2>x1 && x2<x3 || x2<x1 && x2>x3)
   return (lb+ub)/2;

  if(x3>x2 && x3<x1 || x3<x2 && x3>x1)
   return ub;

  return lb;
 }

 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   a = new int[element.length];

   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }  
     
   quickSort(0,a.length-1); //call to quick Sort  
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Heap Sort with left curtailment in Java (Best)

import java.io.*;

class HeapSortLC 
{
 static int[] a;
 static int limit;
 static int constant=1;
 static int c=0,m=0; //variables to keep track of comparisons and moves

 public static void reHeapLightBubble(int k)
 {  
  if( 2*k+constant > a.length-1)
   return;

  if( 2*k+(constant+1) > a.length-1)
  {
   c++;
   if(a[k]>a[2*k+constant])
   {
    swap(k,2*k+constant);
    reHeapLightBubble(2*k+constant);  
   }
   return;
  }
  
  c+=2;

  if(a[2*k+constant]<a[k] || a[2*k+(constant+1)]<a[k])
  {
   c++;
   if(a[2*k+constant]<a[2*k+(constant+1)])
   {
    swap(k,2*k+constant);
    reHeapLightBubble(2*k+constant);
   }
   else
   {
    swap(k,2*k+(constant+1));
    reHeapLightBubble(2*k+(constant+1));
   }
   return;
  }
 }

 public static void swap(int x, int y)
 {
  int temp = a[x];
  a[x] = a[y];
  a[y] = temp;
  m+=3;
 }

 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   a = new int[element.length];

   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }  
     
   //Main logic of heap sort with left curtailment     

   for(int i=a.length-1; i>=0; i--)
   {
     reHeapLightBubble(i);
   }

   constant--;

   for(limit=1; limit<a.length-1; limit++)
   {
    reHeapLightBubble(limit);
    constant--;
   }
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Heap Sort with Partial Heaping in Java

import java.io.*;

class HeapSort 
{
 static int[] a;
 static int limit;
 static int c=0,m=0; //variables to keep track of comparisons and moves

 public static void reHeap(int k)
 {  
  if( 2*k+1 > limit)
   return;

  if( 2*k+2 > limit)
  {
   c++;
   if(a[k]<a[2*k+1])
   {
    swap(k,2*k+1);
    reHeap(2*k+1);  
   }
   return;
  }
  
  c+=2;
  if(a[2*k+1]>a[k] || a[2*k+2]>a[k])
  {
   c++;
   if(a[2*k+1]>a[2*k+2])
   {
    swap(k,2*k+1);
    reHeap(2*k+1);
   }
   else
   {
    swap(k,2*k+2);
    reHeap(2*k+2);
   }
   return;
  }
 }

 public static void swap(int x, int y)
 {
  int temp = a[x];
  a[x] = a[y];
  a[y] = temp;
  m+=3;
 }

 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   a = new int[element.length];

   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }  
     
   //Main logic of heap sort with partial heaping
   limit=a.length-1;
   reHeap(limit);
   swap(0,limit);
   
   limit--;

   for(; limit>0; limit--)
   {
    reHeap(0);
    swap(0,limit);
   }
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Heap Sort in Java

import java.io.*;

class HeapSort 
{
 static int[] a;
 static int limit;
 static int c=0,m=0; //variables to keep track of comparisons and moves

 public static void reHeap(int k)
 {  
  if( 2*k+1 > limit)
   return;

  if( 2*k+2 > limit)
  {
   c++;
   if(a[k]<a[2*k+1])
   {
    swap(k,2*k+1);
    reHeap(2*k+1);  
   }
   return;
  }
  
  c+=2;
  if(a[2*k+1]>a[k] || a[2*k+2]>a[k])
  {
   c++;
   if(a[2*k+1]>a[2*k+2])
   {
    swap(k,2*k+1);
    reHeap(2*k+1);
   }
   else
   {
    swap(k,2*k+2);
    reHeap(2*k+2);
   }
   return;
  }
 }

 public static void swap(int x, int y)
 {
  int temp = a[x];
  a[x] = a[y];
  a[y] = temp;
  m+=3;
 }

 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }  

     
   //Main logic of heap sort
   
   for(limit=a.length-1; limit>0; limit--)
   {
    for(int i=limit; i>=0; i--)
     reHeap(i);

    swap(0,limit);
   }
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Shell Sort in Java

import java.io.*;

class ShellSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   int[] a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }

   int c=0,m=0; //variables to keep track of comparisons and moves

   //Skips for shell sort   
   System.out.print("\nEnter number of skips (Shell Sort): ");   

   int[] skips = new int[Integer.parseInt(br.readLine())];
   
   System.out.println("Enter skips (the last skip value must be 1): ");
   for(int i=0; i<skips.length; i++)
   {
    skips[i] = Integer.parseInt(br.readLine());
   }

   
   //Main logic of shell sort
   
   for(int x=0; x<skips.length; x++)
   {
    int gap=skips[x];

    for(int start=0; start<gap; start++)
    {
     for(int i=gap+start;i<a.length;i+=gap)
     {
      for(int j=start; j<i; j+=gap)
      { 
       c++;
       if(a[i]<a[j])
       {
        int temp = a[i];

        for(int k=i; k>j; k-=gap)
        {
         m++;
         a[k]=a[k-gap];
        }

        m++;
        a[j] = temp;
        break;
       }
      } 
     }   
    }    
   }  
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Shaker Sort in Java

import java.io.*;

class ShakerSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   int[] a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }

   int c=0,m=0; //variables to keep track of comparisons and moves

   
   //Main logic of shaker sort
   
  
   for(int pass=0; pass<a.length/2; pass++)
   {
    boolean flag=true;

    for(int j=pass; j<a.length-pass-1; j++)
    { 
     c++;
     if(a[j]>a[j+1])
     {
      int temp = a[j];
      a[j] = a[j+1];
      a[j+1] = temp;
      m+=3;
      flag=false;
     }
    }

    if(flag)
     break;

    flag=true;

    for(int j=a.length-(pass+2); j>pass; j--)
    {
     c++;
     if(a[j]<a[j-1])
     {
      int temp=a[j];
      a[j]=a[j-1];
      a[j-1]=temp;
      m+=3;
      flag=false;
     }
    }

    if(flag)
     break;
   }

   
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Bubble Sort with Early Exit in Java

import java.io.*;

class BubbleSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   int[] a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }

   int c=0,m=0; //variables to keep track of comparisons and moves

   
   //Main logic of bubble sort with early exit
   

   for(int pass=0; pass<a.length; pass++)
   {
    boolean flag=true;

    for(int j=0; j<a.length-pass-1; j++)
    {
     c++;
     if(a[j]>a[j+1])
     {
      int temp = a[j];
      a[j] = a[j+1];
      a[j+1] = temp;
      m+=3;
      flag=false;
     }
    }

    if(flag)
     break;
   }
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Selection Sort in Java

import java.io.*;

class SelectionSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   int[] a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }

   int c=0,m=0; //variables to keep track of comparisons and moves

   
   //Main logic of selection sort

   for(int i=0; i<a.length-1; i++)
   {
    int min=i;
    for(int j=i+1; j<a.length; j++)
    {
     c++;
     if(a[min]>a[j])
      min=j;
    }

    if(min!=i)
    {
     int temp = a[min];
     a[min] = a[i];
     a[i] = temp;
     m+=3;
    }
   }
   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }

   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

Insertion Sort in Java

import java.io.*;

class InsertionSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());

   char[] buffer = new char[2048];
   int len = fr.read(buffer);

   String data = new String(buffer,0,len);

   String[] element = data.split(",");

   int[] a = new int[element.length];


   System.out.println("\n\nBefore Sorting: ");

   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.println(a[i]);
   }

   int c=0,m=0; //variables to keep track of comparisons and moves


   //Main logic of insertion sort
   for(int i=1; i<a.length; i++)
   {
    for(int j=0;j<i; j++)
    {
     c++;
     if(a[j]>a[i])
     {
      int temp = a[i];
      for(int k=i; k>j; k--)
      {
       a[k] = a[k-1];
       m++;
      }
      
      a[j] = temp;
      m++;      
      break;
     }
    }
   }

   
   System.out.println("\n\nAfter Sorting: ");

   for(int i=0; i<a.length; i++)
   {   
    System.out.println(a[i]);
   }

   System.out.println("\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}

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

Dijkstra Algorithm

Consider each node with a tag associated as (flag, previous, distance); where flag is true if the node is made permanent else false, previous indicates the name of the previous node and distance is the distance of the current node from the start node.

Algorithm 1 (To set the traversal path and find minimum distance)

1. Set  the tags of all the nodes as (F, -, infinity) i.e.
   F -> permanent false
   (dash - ) -> No previous node and
   distance is infinity
2. Accept the start node and set the tag for the start node as (T, -, 0) i.e.
   permanent
   No previous node and
   distance is 0
3. Set the tags of all reachable nodes from start node; previous node is start node and distance from the start node
4. Find  a node with minimum distance and permanent = false; Note: don’t compare with nodes having distance infinity
5. If no such node exists then go to step 9
6. Mark this node permanent i.e. set the permanent flag true
7. Find all reachable nodes from this node
   Dist = this.distance + distance of reachable node from this node
   If distance of the new node is infinity then
   Set the distance = Dist
   Set the previous node = this
   Else
   If (reachable.distance>Dist) then
   Set the distance = Dist
   Set the previous node = this
   End If
   End If
8. Go to Step 4
9. Print traversal path and distance of each node from start node
10. Stop

Algorithm 2 (Print traversal path and distance of each node from start node)

1. Take a node from the tree
2. Print the distance value from tag
3. Print current nod name
4. If distance=0 then go to step 7
5. Current = Current.previous
6. Go to step 3
7. Take next node
8. If node exists then go to step 2
9. Stop