daa

mail@pastecode.io avatarunknown
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();
	}
}