daa
plain_text
22 days ago
5.4 kB
1
Indexable
Never
Floyed---------------------------------- import java.lang.*; import java.util.Scanner; public class Floyd { int d[][]=new int[10][10]; public void dis_path(int n,int a[][]) { for(int i=0;i<n;i++) { for(int j=0; j<n;j++) { d[i][j]=a[i][j]; } } for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { d[i][j]=Math.min(d[i][j],(d[i][k]+d[k][j])); } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { System.out.print(d[i][j]+""); } System.out.println(); } } } public class Floyed { public static void main(String[] args) { int n; int a[][]=new int[10][10]; Scanner sobj=new Scanner(System.in); Floyd f =new Floyd(); System.out.println("****FLOYEDS ALGORITHM****"); System.out.println("Enter the number of nodes:"); n=sobj.nextInt(); System.out.println("Enter the cost adjacency matrix:"); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) a[i][j]=sobj.nextInt(); } System.out.println("Resultant shortest path matrix is:"); f.dis_path(n, a); sobj.close(); } } Krushkal_algo----------------------------------- package maneesha; import java.util.Scanner; public class Krushkal_algo { int n; int a[][]=new int[10][10]; void read_cost_adjacency_matrix() { System.out.println("***********KRUSHKAL ALGPRITHM***************"); System.out.println("Enter the number of nodes"); Scanner scan=new Scanner(System.in); n=scan.nextInt(); System.out.println("Enter the cost adjacency matrix"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { a[i][j]=scan.nextInt(); } } scan.close(); } void find_minimum_spanningtree() { int parent[]=new int[10]; int t[][]=new int[10][3]; for(int i=1;i<=n;i++) { parent[i]=i; } int count=0,sum=0,k=0,u=0,v=0; while(count!=n-1) { int min=999; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]!=0&&a[i][j]<min) { min=a[i][j]; u=i; v=j; } } } if(min==999) break; int i=u; while(parent[i]!=i) i=parent[i]; int j=v; while(parent[j]!=j) j=parent[j]; if(i!=j) { t[k][0]=u; t[k][1]=v; t[k][2]=min; k++; sum=sum+min; parent[j]=i; count++; } a[u][v]=a[v][u]=999; } if(count==n-1) { System.out.println("The min cost spanning tree with rdges is"); System.out.println("***************"); System.out.println("Edge"+"\t"+"Weight"); System.out.println("**************************"); for(int i=0;i<n-1;i++) System.out.println(t[i][0]+"->"+t[i][1]+"\t"+t[i][2]); System.out.println("Cost of the Spanning tree="+sum); } else System.out.println("Spanning tree does not exist"); } } public class kruskal { public static void main(String[] args) { Krushkal_algo k=new Krushkal_algo(); k.read_cost_adjacency_matrix(); k.find_minimum_spanningtree(); } } Prims_algo---------------------------------- import java.util.Scanner; public class Prims_algo { int n; int a[][]=new int[10][10]; void read_adjacency_matrix() { System.out.println("**********PRIMS ALGORITHM*****"); System.out.println("Enter number of nodes"); Scanner scan=new Scanner(System.in); n=scan.nextInt(); System.out.println("enter the cost adjacency matrix"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { a[i][j]=scan.nextInt(); } } scan.close(); } void find_minimum_spanning_tree() { int min,u=0,v=0,k=0,count=0,cost=0,i,j; int visited[]=new int[20]; int t[][]=new int[20][3]; visited[1]=1; while(count!=(n-1)) { for(i=1,min=999;i<=n;i++) { for(j=1;j<-n;j++) { if(visited[i]==1&&visited[j]==0&&min>a[i][j]) { min=a[i][j]; u=i; v=j; } } } if(min==999) break; t[k][0]=u; t[k][1]=v; t[k][2]=min; visited[v]=1; cost+=min; k++; count++; } if(count==n-1) { System.out.println("The min cost spanning tree with edge is"); System.out.println("*********************"); System.out.println("Edge"+"\t"+"Weight"); System.out.println("********************"); for(i=0;i<k;i++) System.out.println(t[i][0]+"->"+t[i][1]+"\t"+t[i][2]); System.out.println("******************"); System.out.println("*cost of spanning tree="+cost); System.out.println("******************"); } else System.out.println("spanning tree does not exist"); } } public class prim { public static void main(String[]args) { Prims_algo p=new Prims_algo(); p.read_adjacency_matrix(); p.find_minimum_spanning_tree(); } }