Dijkstra's algorithm in java

On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in Java:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Graph
{
 int nodes;
 int edges;
 int grph[][];
 
 void accept() throws IOException
 {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Enter number of nodes: ");
  nodes = Integer.parseInt(br.readLine());
  System.out.println("Enter number of edges: ");
  edges = Integer.parseInt(br.readLine());
  grph = new int[nodes][nodes];
  for(int i = 0; i < nodes; i++)
   for(int j = 0; j < nodes; j++)
    grph[i][j] = 9999;
  for(int i = 0; i < edges; i++)
  {
   System.out.println("Enter source node for edge " + (i + 1));
   int source = Integer.parseInt(br.readLine());
   System.out.println("Enter destination node for edge " + (i + 1));
   int destination = Integer.parseInt(br.readLine());
   System.out.println("Enter the distance for traveling from node " + source + " to " + destination);
   int distance = Integer.parseInt(br.readLine());
   grph[source - 1][destination - 1] = distance;
   grph[destination - 1][source - 1] = distance;
  }
 }
}

class Dijkstras {
 
 static void dijk(Graph g, int src)
 {
  int distance[] = new int[g.nodes];
  int previous[] = new int[g.nodes];
  String path[] = new String[g.nodes];
  for(int i = 0; i < g.nodes; i++)
  {
   distance[i] = 9999;
   previous[i] = -1;
   path[i] = "";
  }
  distance[src] = 0;
  for(int i = 0; i < g.nodes; i++)
  {
   for(int j = 0; j < g.nodes; j++)
   {
    if(distance[i] + g.grph[i][j] < distance[j])
    {
     distance[j] = distance[i] + g.grph[i][j];
     previous[j] = i;
    }
   }
  }
  for(int i = 0; i < g.nodes; i++)
  {
   int current = i;
   do
   {
    path[i] = "-" + (current + 1) + path[i];
    current = previous[current];
   }
   while(current != -1);
   path[i] = path[i].substring(1, path[i].length());
  }
  System.out.println();
  for(int i = 0; i < g.nodes; i++)
  {
   if(i != src)
   {
    System.out.println("The shortest path & its distance for node " + (i + 1) + " is:");
    System.out.print("Path: " + path[i]);
    System.out.println(" Distance: " + distance[i]);
   }
  }
 }
 
 public static void main(String args[]) throws IOException
 {
  Graph g = new Graph();
  g.accept();
  dijk(g, 0);
 }
}
output:-
Enter number of nodes: 
6
Enter number of edges: 
9
Enter source node for edge 1
1
Enter destination node for edge 1
6
Enter the distance for traveling from node 1 to 6
14
Enter source node for edge 2
1
Enter destination node for edge 2
3
Enter the distance for traveling from node 1 to 3
9
Enter source node for edge 3
1
Enter destination node for edge 3
2
Enter the distance for traveling from node 1 to 2
7
Enter source node for edge 4
2
Enter destination node for edge 4
3
Enter the distance for traveling from node 2 to 3
10
Enter source node for edge 5
2
Enter destination node for edge 5
4
Enter the distance for traveling from node 2 to 4
15
Enter source node for edge 6
3
Enter destination node for edge 6
6
Enter the distance for traveling from node 3 to 6
2
Enter source node for edge 7
3
Enter destination node for edge 7
4
Enter the distance for traveling from node 3 to 4
11
Enter source node for edge 8
4
Enter destination node for edge 8
5
Enter the distance for traveling from node 4 to 5
6
Enter source node for edge 9
5
Enter destination node for edge 9
6
Enter the distance for traveling from node 5 to 6
9

The shortest path & its distance for node 2 is:
Path: 1-2 Distance: 7
The shortest path & its distance for node 3 is:
Path: 1-3 Distance: 9
The shortest path & its distance for node 4 is:
Path: 1-3-4 Distance: 20
The shortest path & its distance for node 5 is:
Path: 1-3-6-5 Distance: 20
The shortest path & its distance for node 6 is:
Path: 1-3-6 Distance: 11
--------------------------------

0 comments: