import java.lang.*;
import java.util.*;
class ralgo
{
public static void main(String[] args)
{
int i,j,row,k,m;
ralgo ral=new ralgo();
Scanner sc=new Scanner(System.in);
System.out.println(“Enter total no of nodes:”);
int n=sc.nextInt();
int distance[]=new int[n]; //declare distance array to store distance of nodes from source//
int parent[]=new int[n]; //declare parent array //
int visited[]=new int[n]; //this array is used to check whether particular node is visited or not//
int check[][]=new int[n][n];//this is the array where operation takes place//
int iarray[][]=new int[n][n];
System.out.println(“Enter inputs”);
//take input
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
iarray[i][j]=sc.nextInt();
}
}
//display input
System.out.println(“input array is as follows”);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
System.out.print(” “+iarray[i][j]);
}
System.out.println();
}
for(m=0;m<n;m++)
{
visited[m]=0;
parent[m]=0;
}
for(k=0;k<n;k++)
{
check[0][k]=iarray[0][k];
}
visited[0]=1;
for(row=1;row<n;row++)
{
i=ral.smallest(check,row-1,visited,n);
if(i==-1)
{
break;
}
System.out.println(“Smallest no is found at column “+i+” for row no “+(row-1));
visited[i]=1;
distance[i]=check[row-1][i];
System.out.println(“distance[“+i+”] is “+distance[i]);
parent[i]=row-1;
for(j=0;j<n;)
{
if(visited[j]==1)
{
j++;
}
else
{
if(distance[i]+iarray[i][j]<check[row-1][j])
{
check[row][j]=distance[i]+iarray[i][j];
}
else
{
check[row][j]=check[row-1][j];
}
j++;
}
}
}
System.out.println(“distance of each node from source is as follows:”);
for(k=0;k<n;k++)
{
System.out.println(“distance[“+k+”]=”+distance[k]+” whose parent node is “+parent[k]);
}
}
public int smallest(int check[][],int row_no,int visited[],int node)
{
int i=0,j,col_no=-1;
while(i<node && visited[i]==1)
{
i++;
}
if(i<node)
{
col_no=i;
}
j=i+1;
while(j<node)
{
while(j<node && visited[j]==1)
{
j++;
}
if(j<node)
{
if(check[row_no][col_no]>check[row_no][j])
{
col_no=j;
}
}
j++;
}
return col_no;
}
}
OUTPUT:
Enter total no of nodes:
4
Enter inputs
0
2
3
4
2
0
99
1
3
99
0
2
4
1
2
0
input array is as follows
0 2 3 4
2 0 99 1
3 99 0 2
4 1 2 0
Smallest no is found at column 1 for row no 0
distance[1] is 2
Smallest no is found at column 2 for row no 1
distance[2] is 3
Smallest no is found at column 3 for row no 2
distance[3] is 3
distance of each node from source is as follows:
distance[0]=0 whose parent node is 0
distance[1]=2 whose parent node is 0
distance[2]=3 whose parent node is 1
distance[3]=3 whose parent node is 2
Download the file here: Routing Algo
gangof1994 