DESIGN AND ANALYSIS

OF ALGORITHMS

Practical File
COCSC06

Submitted to: Submitted By:

Vijay Kumar Bohat Name : Saneh
Rollno.: 2022UCS1541

NETAJI SUBHASH UNIVERSITY OF TECHNOLOGY

DWARKA SECTOR - 3, DELHI
PIN: 110078
1. Sort a given set of elements using the Quick sort method and determine the time
required to sort the elements. Repeat the experiment for different values of n, the number
of elements in the list to be sorted. The elements can be read from a file or can be
generated using the random number generator.

import java.util.Arrays;
import java.util.Random;
public class Practice {
public static void main(String[] args) {
int[] nValues = {10, 50, 100, 20};
for (int n : nValues) {
int[] array = generateRandomArray(n);
long startTime = System.currentTimeMillis();
quickSort(array, 0, array.length - 1);
long endTime = System.currentTimeMillis();
System.out.println("Sorted array for n=" + n + ": " + Arrays.toString(array));
System.out.println("Time taken to sort for n=" + n + ": " + (endTime - startTime) + "
milliseconds\n");
}
}
private static void quickSort(int[] array, int low, int high) {
if (low < high) {
int partitionIndex = partition(array, low, high);
quickSort(array, low, partitionIndex - 1);
quickSort(array, partitionIndex + 1, high);
}
}
private static int partition(int[] array, int low, int high) {
int pivot = array[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (array[j] <= pivot) {
i++;
int temp = array[i];
array[i] = array[j];
 array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;

return i + 1;
}
private static int[] generateRandomArray(int size) {
int[] array = new int[size];
Random random = new Random();

for (int i = 0; i < size; i++) {

array[i] = random.nextInt(100);
}
return array;
}
}

Output:

2. Implement a Merge Sort algorithm to sort a given set of elements and determine the
time required to sort the elements. Repeat the experiment for different values of n, the
number of elements in the list to be sorted. The elements can be read from a file or can
be generated using the random number generator

import java.util.Arrays;
import java.util.Random;
public class MergeSortExample {
public static void main(String[] args) {
// Change the values in the array to experiment with different sizes
int[] arraySizes = {100, 500, 1000, 5000, 10000};
for (int n : arraySizes) {
int[] arr = generateRandomArray(n);
long startTime = System.nanoTime();
mergeSort(arr);
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1000000; // Convert to milliseconds
System.out.println("Array size: " + n + "\tTime taken: " + duration + " milliseconds");
}
}
private static int[] generateRandomArray(int n) {
int[] arr = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(1000); // You can adjust the range of random numbers as needed
}
return arr;
}
private static void mergeSort(int[] arr) {
if (arr.length > 1) {
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);

mergeSort(left);
mergeSort(right);

merge(arr, left, right);

}
}

private static void merge(int[] arr, int[] left, int[] right) {

 int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}

while (i < left.length) {

arr[k++] = left[i++];
}

while (j < right.length) {

arr[k++] = right[j++];
}
}
}
Output:

Q 3 Write a program to implement Red Black Tree .

import java.io.*;

public class RedBlackTree {

public Node root; // Root node

public RedBlackTree() {
super();
root = null;
}
// Node class representing the elements of the tree
class Node {
int data;
Node left;
Node right;
char colour; // 'R' for red, 'B' for black
Node parent;

Node(int data) {
super();
this.data = data;
this.left = null;
this.right = null;
this.colour = 'R'; // Initializing the node color to red
this.parent = null;
}
}

// Function to perform left rotation

Node rotateLeft(Node node) {
Node x = node.right;
Node y = x.left;
x.left = node;
node.right = y;
node.parent = x;

if (y != null) {
y.parent = node;
}

return x;
}

// Function to perform right rotation

Node rotateRight(Node node) {
 Node x = node.left;
Node y = x.right;
x.right = node;
node.left = y;
node.parent = x;

if (y != null) {
y.parent = node;
}

return x;
}

// Helper function for insertion

Node insertHelp(Node root, int data) {
boolean f = false; // Flag for checking RED RED conflict
// Recursive calls to insert at the proper position according to BST properties
if (root == null)
return (new Node(data));
else if (data < root.data) {
root.left = insertHelp(root.left, data);
root.left.parent = root;

if (root != this.root) {
if (root.colour == 'R' && root.left.colour == 'R') {
f = true;
}
}
} else {
root.right = insertHelp(root.right, data);
root.right.parent = root;

if (root != this.root) {
if (root.colour == 'R' && root.right.colour == 'R') {
f = true;
}
 }
}

// Perform rotations and recoloring if needed

// ... (Rotation logic)
// ...

// Handling RED RED conflict

if (f) {
// Logic to handle conflicts
// ...
}

return root;
}

// Function to insert data into the tree

public void insert(int data) {
if (this.root == null) {
this.root = new Node(data);
this.root.colour = 'B'; // Setting root color to black
} else {
this.root = insertHelp(this.root, data);
}
}

// Helper function for inorder traversal

void inorderTraversalHelper(Node node) {
if (node != null) {
inorderTraversalHelper(node.left);
System.out.printf("%d ", node.data);
inorderTraversalHelper(node.right);
}
}

// Function to print inorder traversal

 public void inorderTraversal() {
inorderTraversalHelper(this.root);
}

// Helper function to print the tree

void printTreeHelper(Node root, int space) {
// Logic to print the tree structure
// ...
}

// Function to print the tree

public void printTree() {
printTreeHelper(this.root, 0);
}

public static void main(String[] args) {

RedBlackTree t = new RedBlackTree();
int[] arr = { 1, 4, 6, 3, 5, 7, 8, 2, 9 };

for (int i = 0; i < 9; i++) {

t.insert(arr[i]);

t.inorderTraversal();
System.out.println();
}

t.printTree();
}
}

OUTPUT :
4. Implement Radix Sort and Bucket Sort algorithms and compare their performance on a
set of randomly generated integers.
public class Practice {
public static void radixSort(int[] array) {
int max = Arrays.stream(array).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(array, exp);
}
}
private static void countingSort(int[] array, int exp) {
int n = array.length;
int[] output = new int[n];
int[] count = new int[10];
Arrays.fill(count, 0);
for (int i = 0; i < n; i++) {
count[(array[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(array[i] / exp) % 10] - 1] = array[i];
count[(array[i] / exp) % 10]--;
}
System.arraycopy(output, 0, array, 0, n);
}
public static void bucketSort(int[] array) {
int max = Arrays.stream(array).max().getAsInt();
 int min = Arrays.stream(array).min().getAsInt();
int range = max - min + 1;
int bucketSize = 5;
int bucketCount = (range / bucketSize) + 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new LinkedList<>());
}
for (int value : array) {
int bucketIndex = (value - min) / bucketSize;
buckets.get(bucketIndex).add(value);
}
int currentIndex = 0;
for (List<Integer> bucket : buckets) {
insertionSort(bucket);
for (int value : bucket) {
array[currentIndex++] = value;
}
}
}
private static void insertionSort(List<Integer> bucket) {
for (int i = 1; i < bucket.size(); i++) {
int current = bucket.get(i);
int j = i - 1;
while (j >= 0 && bucket.get(j) > current) {
bucket.set(j + 1, bucket.get(j));
j--;
}
bucket.set(j + 1, current);
}
}
public static void main(String[] args) {
int[] array = generateRandomArray(100000, 1, 100000);
long startTimeRadix = System.currentTimeMillis();
radixSort(array.clone());
long endTimeRadix = System.currentTimeMillis();
 System.out.println("Radix Sort Time: " + (endTimeRadix - startTimeRadix) + " ms");
long startTimeBucket = System.currentTimeMillis();
bucketSort(array.clone());
long endTimeBucket = System.currentTimeMillis();
System.out.println("Bucket Sort Time: " + (endTimeBucket - startTimeBucket) + " ms");
}
private static int[] generateRandomArray(int size, int minValue, int maxValue) {
int[] array = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(maxValue - minValue + 1) + minValue;
}
return array;
}
}
Output:

5. Provide solution for knapsack problem using greedy method.

import java.util.Arrays;
import java.util.Comparator;

class Item {
int weight;
int value;

public Item(int weight, int value) {

this.weight = weight;
this.value = value;
}
}

public class Practice {

public static double knapsackGreedy(Item[] items, int capacity) {
Arrays.sort(items, Comparator.comparingDouble(item -> -1.0 * item.value / item.weight));
int currentWeight = 0;
double finalValue = 0.0;
 for (Item item : items) {
if (currentWeight + item.weight <= capacity) {
currentWeight += item.weight;
finalValue += item.value;
} else {
int remainingCapacity = capacity - currentWeight;
finalValue += (double) item.value * remainingCapacity / item.weight;
break;
}
}
return finalValue;
}
public static void main(String[] args) {
Item[] items = {
new Item(2, 10),
new Item(5, 20),
new Item(10, 30),
new Item(5, 8),
new Item(8, 15)
};
int capacity = 25;
double maxValue = knapsackGreedy(items, capacity);
System.out.println("Maximum value in Knapsack = " + maxValue);
}
}
Output:

6.
A) Obtain the Topological ordering of vertices in a given digraph.
public class topologiclasort {
static class Edge{
int src;
int dest;
public Edge(int src,int dest){
this.src=src;
this.dest=dest;
 }
}
public static void createGraph(ArrayList<Edge> graph[]){
for(int i=0;i<graph.length;i++){
graph[i]=new ArrayList<>();
}
graph[0].add(new Edge(0,3));
graph[2].add(new Edge(2,3));
graph[3].add(new Edge(3,1));
graph[4].add(new Edge(4,1));
graph[4].add(new Edge(4,0));
graph[5].add(new Edge(5,0));
graph[5].add(new Edge(5,2));
}
public static void topSort(ArrayList<Edge> graph[]){
boolean vis[]=new boolean[graph.length];
Stack<Integer> st=new Stack<>();
for(int i=0;i<graph.length;i++){
if(!vis[i]) topSortUtil(graph,i,vis,st);
}
while(!st.isEmpty()) System.out.print(st.pop()+" ");
}
public static void topSortUtil(ArrayList<Edge> graph[],int curr,boolean vis[],Stack<Integer>
st){
vis[curr]=true;
for(int i=0;i<graph[curr].size();i++){
Edge e=graph[curr].get(i);
if(!vis[e.dest]) topSortUtil(graph,e.dest,vis,st);
}
st.push(curr);
}
Output:

B) Compute the transitive closure of a given directed graph using Warshall's

algorithm
public class WarshallAlgorithm {
 public static void main(String[] args) {
int[][] graph = {
{0, 1, 0, 0},
{0, 0, 0, 1},
{1, 0, 0, 0},
{0, 0, 1, 0}
};
int[][] transitiveClosure = computeTransitiveClosure(graph);
for (int i = 0; i < transitiveClosure.length; i++) {
for (int j = 0; j < transitiveClosure[0].length; j++) {
System.out.print(transitiveClosure[i][j] + " ");
}
System.out.println();
}
}
public static int[][] computeTransitiveClosure(int[][] graph) {
int numVertices = graph.length;
int[][] closure = new int[numVertices][numVertices];
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
closure[i][j] = graph[i][j];
}
}
for (int k = 0; k < numVertices; k++) {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j]);
}
}
}
return closure;
}
}
Output:
7.Implement 0/1 Knapsack problem using Dynamic Programming.
static int unboundedKnapsack(int val[],int wt[],int W){
int n=val.length;
int dp[][]=new int[n+1][W+1];
for(int i=0;i<n+1;i++) dp[i][0]=0;
for(int j=0;j<dp[0].length;j++) dp[0][j]=0;
for(int i=1;i<n+1;i++){
for(int j=1;j<W+1;j++){
if(wt[i-1]<=j){
dp[i][j]=Math.max(val[i-1]+dp[i][j-wt[i-1]],dp[i-1][j]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[n][W];
}
Output:

8. From a given vertex in a weighted connected graph, find shortest paths to other
vertices using Dijikstra’s algorithm
public static void dijkstra(ArrayList<Edge> graph[],int src){
int dist[]=new int[graph.length];
for(int i=0;i<graph.length;i++) {
if(i!=src){
dist[i]=Integer.MAX_VALUE;
}
}
 boolean vis[]=new boolean[graph.length];
PriorityQueue<Pair> pq=new PriorityQueue<>();
pq.add(new Pair(src,0));
while(!pq.isEmpty()){
Pair curr=pq.remove();
if(!vis[curr.n]){
vis[curr.n]=true;
for(int i=0;i<graph[curr.n].size();i++){
Edge e=graph[curr.n].get(i);
int u=e.src;
int v=e.dest;
int wt=e.wt;
if(dist[u]+wt<dist[v]){
dist[v]=dist[u]+wt;
pq.add(new Pair(v,dist[v]));
}
}
}
}
for(int i=0;i<dist.length;i++){
System.out.print(dist[i]+" ");
}
}
Output:

9. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.

/* DISJOINT SET DATA STRUCTURE IMPLEMENTATION */

static int n = 4;
static int par[] = new int[n];
public static void init(int par[]){
for(int i = 0;i<par.length;i++){
par[i]=i;
}
}
static int rank[] = new int[n];
// find function in disjoint data structure
public static int find(int x) { //o(1)
if(x==par[x]){
return x;
}
return find(par[x]);
}
// union function
public static void union(int x , int y){ //o(1)
int parX = find(x);
int parY = find(y);
if(rank[parX] == rank[parY]){
par[parX] = parY;
rank[parY]++;
} else if(rank[parX]<rank[parY]) {
par[parX] = parY;
} else {
par[parY] = parX;
}
}
public static void kruskalsMST(ArrayList<Edge> edges, int V) {
init(par);
Collections.sort(edges);
int mstans = 0;
int count = 0;
for(int i = 0;count<V-1;i++){
Edge e = edges.get(i);
int parX = find(e.src);
int parY = find(e.dest);
if(parX != parY){
union(e.src , e.dest);
mstans += e.wt;
System.out.print(mstans+" ");
count++;
 System.out.println(e.src + " ," + e.dest);
}
}
System.out.println(mstans);
}
public static void createGraphonlyEdges(ArrayList<Edge> edges){
edges.add(new Edge(0, 1, 10));
edges.add(new Edge(0, 2, 15));
edges.add(new Edge(0, 3, 30));
edges.add(new Edge(1, 3, 40));
edges.add(new Edge(2, 3, 50));

Output:

10.
(A) Print all the nodes reachable from a given starting node in a digraph using BFS method.
public class BFSGraph {
private int vertices;
private ArrayList<Integer>[] adjList;
public BFSGraph(int vertices) {
this.vertices = vertices;
adjList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new ArrayList<>();
}
}
public void addEdge(int source, int destination) {
adjList[source].add(destination);
}
public void BFS(int startNode) {
boolean[] visited = new boolean[vertices];
 Queue<Integer> queue = new LinkedList<>();
visited[startNode] = true;
queue.add(startNode);
while (!queue.isEmpty()) {
int currentNode = queue.poll();
System.out.print(currentNode + " ");
for (int neighbor : adjList[currentNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
BFSGraph graph = new BFSGraph(7);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
int startNode = 0;
System.out.println("BFS starting from node " + startNode + ":");
graph.BFS(startNode);
}
}
Output:

(B) Check whether a given graph is connected or not using DFS method.

public class ConnectedGraphDFS {

private int vertices;
private ArrayList<Integer>[] adjList;
 public ConnectedGraphDFS(int vertices) {
this.vertices = vertices;
adjList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new ArrayList<>();
}
}
public void addEdge(int source, int destination) {
adjList[source].add(destination);
adjList[destination].add(source); // For undirected graph
}
public boolean isConnected() {
boolean[] visited = new boolean[vertices];
int startNode = 0;
DFS(startNode, visited);
for (boolean nodeVisited : visited) {
if (!nodeVisited) {
return false; // Graph is not connected
}
}
return true; // Graph is connected
}
private void DFS(int startNode, boolean[] visited) {
Stack<Integer> stack = new Stack<>();
stack.push(startNode);
visited[startNode] = true;
while (!stack.isEmpty()) {
int currentNode = stack.pop();
for (int neighbor : adjList[currentNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
}
public static void main(String[] args) {
ConnectedGraphDFS graph = new ConnectedGraphDFS(7);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
boolean isConnected = graph.isConnected();
if (isConnected) {
System.out.println("The graph is connected.");
} else {
System.out.println("The graph is not connected.");
}
}
}

Output:

Q 11 Find a subset of a given set S of n integers whose sum is equal to a given positive
integer d . For example , if S = {1,2,5,6,8} and d= 9 there are two solutions {1,2,6} and {1,8}
. A suitable message is to be dislayed if the given problem instance doesn’t have a
solution .

import java.util.*;

public class ques11 {

public static void findSubsets(int[] set, int i, int sum, List<Integer> subset, List<List<Integer>>
subsets) {
if (sum == 0) {
subsets.add(new ArrayList<>(subset));
return;
 }

if (i == set.length || sum < 0)

return;

findSubsets(set, i+1, sum, subset, subsets);

subset.add(set[i]);
int s = sum - set[i];
findSubsets(set,i+1, s, subset, subsets);
subset.remove(subset.size() - 1);
}

public static void main(String[] args) {

int[] set = {1, 2, 5, 6, 8};
int d = 9;
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> subset = new ArrayList<>();

findSubsets(set, 0, d, subset, subsets);

if (subsets.size() == 0) {
System.out.println("No subset found with the given sum");
} else {
System.out.println("Subsets with sum " + d + ":");
for (List<Integer> sub : subsets) {
System.out.println(sub);
}
}
}
}

Output :
Q 12 Implement any scheme to find the optimal solution for the Traveling Salesperson
problem and then solve the same problem instance using any approximation algorithm
and determine the error in the approximation.
import java.util.Arrays;
public class abc {
static int[][] adjacencyMatrix = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
static int n = adjacencyMatrix.length;
static int[][] memo;
public static void main(String[] args) {
memo = new int[n][1 << n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
int[] approxTour = nearestNeighbor();
System.out.println("Approximation Tour Length: " + calculateTourLength(approxTour));
int optimalTourLength = tsp(0, 1);
System.out.println("Optimal Tour Length: " + optimalTourLength);
}
public static int tsp(int currentCity, int visited) {
if (visited == (1 << n) - 1) {
return adjacencyMatrix[currentCity][0];
}
if (memo[currentCity][visited] != -1) {
return memo[currentCity][visited];
}
int minDistance = Integer.MAX_VALUE;
for (int nextCity = 0; nextCity < n; nextCity++) {
if ((visited & (1 << nextCity)) == 0) {
int newVisited = visited | (1 << nextCity);
int distance = adjacencyMatrix[currentCity][nextCity] + tsp(nextCity, newVisited);
 minDistance = Math.min(minDistance, distance);
}
}
memo[currentCity][visited] = minDistance;
return minDistance;
}

public static int[] nearestNeighbor() {

int n = adjacencyMatrix.length;
boolean[] visited = new boolean[n];
int[] tour = new int[n];
tour[0] = 0; // Start from city 0
visited[0] = true;

for (int i = 1; i < n; i++) {

int currentCity = tour[i - 1];
int nextCity = findNearestNeighbor(currentCity, visited);
tour[i] = nextCity;
visited[nextCity] = true;
}
tour[n - 1] = tour[0];
return tour;
}
public static int findNearestNeighbor(int city, boolean[] visited) {
int n = adjacencyMatrix.length;
int nearestNeighbor = -1;
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (!visited[i] && adjacencyMatrix[city][i] < minDistance) {
minDistance = adjacencyMatrix[city][i];
nearestNeighbor = i;
}
}
return nearestNeighbor;
}
public static double calculateTourLength(int[] tour) {
 double length = 0;
for (int i = 0; i < tour.length - 1; i++) {
length += adjacencyMatrix[tour[i]][tour[i + 1]];
}
return length;
}
}

Output:

Q 13 Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s
algorithm .
import java.util.*;
public class ques13 {

static class Pair implements Comparable<Pair>{

int v;
int cost ;
public Pair(int v , int cost){
this.v = v;
this.cost = cost;
}
@Override
public int compareTo(Pair p2){
return this.cost - p2.cost;
}

static class Edge{

int src;
int dest;
int wt;
 public Edge(int src , int dest , int wt){
this.src= src ;
this.dest = dest ;
this.wt = wt;
}
}

public static void createGraph(ArrayList<Edge> graph[]){

graph[0].add(new Edge(0,1,10));
graph[0].add(new Edge(0,2,15));
graph[0].add(new Edge(0,3,30));

graph[1].add(new Edge(1,0,10));
graph[1].add(new Edge(1,3,40));

graph[2].add(new Edge(2,0,15));
graph[2].add(new Edge(2,3,50));

graph[3].add(new Edge(3,0,30));
graph[3].add(new Edge(3,1,40));
graph[3].add(new Edge(3,2,50));
}

public static void prims(ArrayList<Edge> graph[]){

boolean vis[] = new boolean[graph.length];

PriorityQueue<Pair> pq = new PriorityQueue<>();

pq.add(new Pair(0,0));
int finalCost =0;

while(!pq.isEmpty()){
Pair curr = pq.remove();
if(!vis[curr.v]){
vis[curr.v] = true;
finalCost += curr.cost;
 for(int i=0 ; i<graph[curr.v].size() ; i++){
Edge e = graph[curr.v].get(i);
pq.add(new Pair(e.dest,e.wt));
}
}
}

System.out.println("The cost is : "+finalCost);

}

public static void main(String args[]){

@SuppressWarnings("unchecked")
ArrayList<Edge> graph[] = new ArrayList[7];

for(int i=0 ; i<graph.length ; i++){

graph[i] = new ArrayList<>();
}
createGraph(graph);
prims(graph);

OUTPUT :

Q 14 Implement All-Pairs Shortest Paths Problems using Floyd’s algorithm .

class ques14{

public static void printAns(int[][] dist){

for(int i=0 ; i<dist.length ; i++){
for(int j=0 ; j<dist.length ; j++){
if(dist[i][j]==9999){
System.out.print("INF ");
 }else{
System.out.print(dist[i][j]+" ");
}
}
System.out.println();
}
}

public static void floyd(int[][] graph){

int V = graph.length ;
int[][] dist = new int[V][V];

for(int i=0 ; i<V; i++){

for(int j=0 ; j<V ; j++){
dist[i][j] = graph[i][j];
}
}

for(int i=0 ; i<V ; i++){

for(int j=0 ; j<V ; j++){
for(int k=0 ; k<V ; k++){
if(dist[i][k]+dist[k][j] < dist[i][j]){
dist[i][j] = dist[i][k]+dist[k][j];
}
}
}
}

printAns(dist);
}
public static void main(String args[]){
int[][] graph = {{0,2,4,9999},
{2,0,1,3},
{4,1,0,5},
{9999,3,5,0}};
floyd(graph);
 }
}

OUTPUT :