Posted by : Unknown
Friday, 26 June 2015
import java.io.*;
class ShortPath
{
public int vertex;
public int edge;
public int arrval[][]=new int[10][10];
public int neigh[]=new int[10];
public int nonnei[]=new int[10];
public int tempnei,ntnei;
public void getdata() throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("ENTER NO OF VERTEX==>");
vertex=Integer.parseInt(br.readLine());
System.out.println("ENTER NO OF EDGE==>");
edge=Integer.parseInt(br.readLine());
for(int i=0;i<vertex;i++)
{
for(int j=0;j<vertex;j++)
{
if(i==j)
arrval[i][j]=0;
else
arrval[i][j]=999;
}
}
for(int k=0;k<edge;k++)
{
System.out.println("ENTER THE EDGE V1-V2");
int v1=Integer.parseInt(br.readLine());
int v2=Integer.parseInt(br.readLine());
System.out.println("ENTER THE EDGE COST==>");
int cost=Integer.parseInt(br.readLine());
arrval[v1][v2]=cost;
arrval[v2][v1]=cost;
}
}
public void process()throws Exception
{
int i,j,k;
for(i=0;i<vertex;i++)
{
tempnei=0;
ntnei=0;
for(j=0;j<vertex;j++)
{
if(arrval[i][j]!=0 && arrval[i][j]!=999)
tempnei++;
else
ntnei++;
}
neigh[i]=tempnei;
nonnei[i]=ntnei;
}
for(k=0;k<vertex;k++)
{
System.out.println("THE NUMBER OF NEIGHBOUR VERTEX==>"+neigh[k]);
System.out.println("THE NUMBER OF NON-NEIGHBOUR VERTEX==>"+nonnei[k]);
}
for(k=0;k<vertex;k++)
{
for(i=0;i<vertex;i++)
{
for(j=0;j<vertex;j++)
{
arrval[i][j]=min(arrval[i][j],arrval[i][k]+arrval[k][j]);
}
}
}
}
public void display()throws Exception
{
System.out.println("SHORTEST PATH");
System.out.println();
for(int i=0;i<vertex;i++)
{
for(int j=0;j<vertex;j++)
{
System.out.print(arrval[i][j]+"\t");
}
System.out.println();
}
}
public int min(int a,int b)
{
int c=a<b?a:b;
return c;
}
public static void main(String arg[])throws Exception
{
ShortPath s=new ShortPath();
s.getdata();
s.display();
s.process();
s.display();
}
}
class ShortPath
{
public int vertex;
public int edge;
public int arrval[][]=new int[10][10];
public int neigh[]=new int[10];
public int nonnei[]=new int[10];
public int tempnei,ntnei;
public void getdata() throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("ENTER NO OF VERTEX==>");
vertex=Integer.parseInt(br.readLine());
System.out.println("ENTER NO OF EDGE==>");
edge=Integer.parseInt(br.readLine());
for(int i=0;i<vertex;i++)
{
for(int j=0;j<vertex;j++)
{
if(i==j)
arrval[i][j]=0;
else
arrval[i][j]=999;
}
}
for(int k=0;k<edge;k++)
{
System.out.println("ENTER THE EDGE V1-V2");
int v1=Integer.parseInt(br.readLine());
int v2=Integer.parseInt(br.readLine());
System.out.println("ENTER THE EDGE COST==>");
int cost=Integer.parseInt(br.readLine());
arrval[v1][v2]=cost;
arrval[v2][v1]=cost;
}
}
public void process()throws Exception
{
int i,j,k;
for(i=0;i<vertex;i++)
{
tempnei=0;
ntnei=0;
for(j=0;j<vertex;j++)
{
if(arrval[i][j]!=0 && arrval[i][j]!=999)
tempnei++;
else
ntnei++;
}
neigh[i]=tempnei;
nonnei[i]=ntnei;
}
for(k=0;k<vertex;k++)
{
System.out.println("THE NUMBER OF NEIGHBOUR VERTEX==>"+neigh[k]);
System.out.println("THE NUMBER OF NON-NEIGHBOUR VERTEX==>"+nonnei[k]);
}
for(k=0;k<vertex;k++)
{
for(i=0;i<vertex;i++)
{
for(j=0;j<vertex;j++)
{
arrval[i][j]=min(arrval[i][j],arrval[i][k]+arrval[k][j]);
}
}
}
}
public void display()throws Exception
{
System.out.println("SHORTEST PATH");
System.out.println();
for(int i=0;i<vertex;i++)
{
for(int j=0;j<vertex;j++)
{
System.out.print(arrval[i][j]+"\t");
}
System.out.println();
}
}
public int min(int a,int b)
{
int c=a<b?a:b;
return c;
}
public static void main(String arg[])throws Exception
{
ShortPath s=new ShortPath();
s.getdata();
s.display();
s.process();
s.display();
}
}
Output:
ENTER NO OF VERTEX==>
2
ENTER NO OF EDGE==>
2
ENTER THE EDGE V1-V2
2
3
ENTER THE EDGE COST==>
5
ENTER THE EDGE V1-V2
2
3
ENTER THE EDGE COST==>
6
SHORTEST PATH
0 999
999 0
THE NUMBER OF NEIGHBOUR VERTEX==>0
THE NUMBER OF NON-NEIGHBOUR VERTEX==>2
THE NUMBER OF NEIGHBOUR VERTEX==>0
THE NUMBER OF NON-NEIGHBOUR VERTEX==>2
SHORTEST PATH
0 999
999 0