DAA
Experiment No.1 Heap sort
Aim:- Program to implement Heap sort
Objective: To write a C program to perform Heap sort using the divide and conquer technique
Theory: A max (min) heap is complete binary tree with the property that the value at each node is at least as large as (as small as) the values at its children (if they exist) Call this property the heap property.
Algorithm:
Step 1: Start the process. Step 2: Declare the variables.
Step 3: Enter the list of elements to be sorted using the get function.
Step 4: Divide the array list into two halves the lower array list and upper array list using the merge sort function.
Step 5: Sort the two array list.
Step 6: Combine the two sorted arrays.
Step 7: Display the sorted elements using the get() function. Step 8: Stop the process
/* Program for Heapsort*/
#include<stdio.h>
void heapsort(int[],int); void heapify(int[],int); void adjust(int[],int); void main() {
int n,i,a[50]; clrscr();
printf("\nEnter the limit:"); scanf("%d",&n);
printf("\nEnter the elements:"); for (i=0;i<n;i++) scanf("%d",&a[i]); heapsort(a,n);
printf("\nThe Sorted Elements Are:\n"); for (i=0;i<n;i++)
printf("\n %d",a[i]); printf("\n");
getch();
}
void heapsort(int a[],int n) { int i,t;
heapify(a,n);
for (i=n-1;i>0;i--) {
t = a[0]; a[0] = a[i]; a[i] = t;
adjust(a,i);
}
}
void heapify(int a[],int n) { int k,i,j,item;
for (k=1;k<n;k++) {
item = a[k]; i = k;
j = (i-1)/2; while((i>0)&&(item>a[j])) {
a[i] = a[j]; i = j;
j = (i-1)/2;
}
a[i] = item;
}
}
void adjust(int a[],int n) { int i,j,item;
j = 0;
item = a[j]; i = 2*j+1;
while(i<=n-1) {
if(i+1 <= n-1) if(a[i] <a[i+1]) i++;
if(item<a[i]) {
a[j] = a[i]; j = i;
i = 2*j+1;
} else
break;
}
a[j] = item;
}
Experiment No.2 Binary Search
Aim:- Program to find the given element in Binary Search Tree.
Objective: To write a C program to perform binary search using the divide and conquer technique.
Theory: A binary search tree is a binary tree. It may be empty. If it is not empty, then it satisfies the following properties:
1. Every element has a key and no two elements have the same key.
2. The keys (if any) in the left sub tree are smaller than the key in the root.
3. The keys (if any) in the right sub tree are larger than the key in the root.
4. The left and right sub trees are also binary search trees.
Algorithm:
Step 1: Start the process. Step 2: Declare the variables.
Step 3: Enter the list of elements to be searched using the get function.
Step 4: Divide the array list into two halves the lower array list and upper arraylist. Step 5: It works by comparing a search key k with the arrays middle element a[m]. Step 6: If they match the algorithm stops; otherwise the same operation is repeated recursively for the first half of the array if k < a[m] and the second half if k > a[m].
Step 7: Display the searching results Step 8: Stop the process.
/* program for binary search*/
#include <stdio.h> Void main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n"); scanf("%d",&n);
printf("Enter %d integers\n", n);
for(c =0; c < n;c++) scanf("%d",&array[c]);
printf("Enter value to find\n"); scanf("%d",&search);
first =0; last = n -1;
middle =(first+last)/2;
while(first <= last){ if(array[middle]< search)
first = middle +1;
else if(array[middle]== search){
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle -1;
middle =(first + last)/2;
}
if(first > last)
printf("Not found! %d is not present in the list.\n", search);
getch();
}
OUTPUT:
Time complexities: -For Searching the element the worst case time complexity is O(n)
and average case is O(log n).
Conclusion: Hence we have found the given element in the binary search tree.
Experiment No.3 Quick Sort
Aim:- Program to implement Quick sort.
Objective: To write a C program to perform Quick sort using the divide and conquer technique
Theory: Quick Sort divides the array according to the value of elements. It rearranges elements of a given array A[0..n-1] to achieve its partition, where the elements before position s are smaller than or equal to A[s] and all the elements after position s are greater than or equal to A[s].
Algorithm:
Step 1: Start the process. Step 2: Declare the variables.
Step 3: Enter the list of elements to be sorted using the get()function.
Step 4: Divide the array list into two halves the lower array list and upper array list using the merge sort function.
Step 5: Sort the two array list.
Step 6: Combine the two sorted arrays. Step 7: Display the sorted elements.
Step 8: Stop the process.
// C program to sort an array using Quick Sort Algorithm //
#include <stdio.h> #include <conio.h> void qsort();
int n;
void main()
{
int a[100],i,l,r; clrscr();
printf("\nENTER THE SIZE OF THE ARRAY: ");
scanf("%d",&n); for(i=0;i<n;i++)
{
printf("\nENTER NUMBER-%d: ",i+1);
scanf("%d",&a[i]);
}
printf("\nTHE ARRAY ELEMENTS BEFORE SORTING: \n");
for(i=0;i<n;i++)
{
printf("%5d",a[i]);
} l=0;
r=n-1;
qsort(a,l,r);
printf("\nTHE ARRAY ELEMENTS AFTER SORTING: \n");
for(i=0;i<n;i++)
printf("%5d",a[i]); getch();
}
void qsort(int b[],int left,int right)
{
int i,j,p,tmp,finished,k; if(right>left)
{
i=left; j=right; p=b[left]; finished=0;
while (!finished)
{
do
{
++i;
}
while ((b[i]<=p) && (i<=right));
while ((b[j]>=p) && (j>left))
{
}
if(j<i)
else
{
--j;
finished=1; tmp=b[i];
b[i]=b[j]; b[j]=tmp;
}
}
tmp=b[left]; b[left]=b[j]; b[j]=tmp; qsort(b,left,j-1); qsort(b,i,right);
}
return;
}
Output:
Time complexities: -Quick sort has an average time of O(n log n) on n elements. Its worst case time is O(n²)
Conclusion: Thus the C program to perform Quick sort using the divide and conquer technique has been completed successfully
Experiment No.4 Maximum and minimum
Aim:- Program to find out maximum and minimum using divide and conquer rule.
Objective: To write a C program to find out maximum and minimum using the divide and conquer technique
Theory: The problem is to find the maximum and minimum number using the divide and conquer method.
Algorithm:
//Program to find out max and min using divide and conquer rule
#include<conio.h> #include<stdio.h> int main()
{
int i,j,a[100],max=0,min=1000,mid,n,max1,max2,min1,min2; printf("enter the size of the array");
scanf("%d",&n);
printf("enter the elements of the array"); for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
j=n-1; int p=0; if(p==j)
{
max=min=a[p];//wen der is only one element in array printf("max is:%d and min is :%d",max,min);
}
else if(p==j-1)
{
if(a[p]<a[j])
{
max=a[j];
min=a[p];
}
else
{
max=a[p];
min=a[j];
}
printf("max is:%d and min is :%d",max,min);
}
else
{
mid=(int)((p+j)/2); for(i=0;i<mid;i++)
{
if(a[i]>max)
{
max=a[i];
}
if(a[i]<min)
{
min=a[i];
}
}
max1=max; min1=min;
printf("\nmax1 is :%d\n",max1); printf("\n min1 is :%d\n",min1); max=0;
min=1000; for(i=mid;i<n;i++)
{
if(a[i]>max)
{
max=a[i];
}
if(a[i]<min)
{
min=a[i];
}
}
max2=max; min2=min;
printf("\nmax2 is :%d\n",max2); printf("\n min2 is :%d\n",min2);
if(max1<max2)
{
max=max2;
}
else max=max1; if(min1<min2)
{
min=min1;
}
else
{
min=min2;
}
printf("\nmaximum is:%d\n",max); printf("\n minimun is:%d\n",min);
}
getch(); return 0;
}
OUTPUT:
Conclusion: Thus the Program to find out maximum and minimum using divide and conquer rule has been completed successfully.
Experiment No.5 Merge Sort
Aim:- Program to implement Merge Sort.
Objective: To write a C program to perform merge sort using the divide and conquer technique.
Theory: .As another example of Divide and conquer a sorting algorithm that in the worst case its complexity is O(n log n). This algorithm is called Merge Sort. Merge sort describes this process using recursion and a function Merge which merges two sorted sets.
Algorithm:
Merge sort is a perfect example of a successful application of the divide-and-conquer technique.
1. Split array A[1..n] in two and make copies of each half in arrays B[1.. n/2 ] and C[1..
n/2 ]
2. Sort arrays B and C
3. Merge sorted arrays B and C into array A as follows:
a) Repeat the following until no elements remain in one of the arrays:
i. compare the first elements in the remaining unprocessed portions of the arrays
ii. copy the smaller of the two into A, while incrementing the index indicating the unprocessed portion of that array
b) Once all elements in one of the arrays are processed, copy the remaining unprocessed elements from the other array into A.
//Program to implement merge sort using Divide and conquer
#include<stdio.h> #include<conio.h> int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid; if(low<high)
{
mid=(low+high)/2; merge_sort(low,mid);
merge_sort(mid+1,high); merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k; h=low;
i=low; j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h]; h++;
}
else
{
b[i]=a[j]; j++;
} i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k]; i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k]; i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
}
int main()
{
int num,i;
printf("\t\t\tMERGE SORT\n"); printf("\nEnter the total numbers: "); scanf("%d",&num);
printf("\nEnter %d numbers: \n",num); for(i=1;i<=num;i++)
{
scanf("%d",&a[i]);
}
merge_sort(1,num); printf("\nSORTED ORDER: \n");
for(i=1;i<=num;i++) printf("\t%d",a[i]); getch();
}
OUTPUT:
Time Complexities:-
All cases have same efficiency: Θ( n log n), Space requirement: Θ( n ) (NOT in-place)
Conclusion:- Thus the C program to perform merge sort using the divide and conquer technique has executed successfully.
Experiment No.6 Knapsack Problem
Aim:- Program to implement Knapsack problem
Objective: To write a C program to solve knapsack problem using Greedy method
Theory:
Algorithm:
Step1: Start the program. Step2: Declare the variable.
Step3: Using the get function read the number of items, capacity of the bag, Weight of the item and value of the items.
Step4: Find the small weight with high value using the find function. Step5: Find the optimal solution using the function findop ().
Step6: Display the optimal solution for the items. Step7: Stop the process
// Program to implement Knapsack problem using Greedy method
# include<stdio.h>
void knapsack(int n, float weight[], float profit[], float capacity) { float x[20], tp = 0;
int i, j, u;
u = capacity;
for (i = 0; i < n; i++) x[i] = 0.0;
for (i = 0; i < n; i++) { if (weight[i] > u)
break; else {
x[i] = 1.0;
tp = tp + profit[i]; u = u - weight[i];
}
}
if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * profit[i]);
printf("\nThe result vector is:- "); for (i = 0; i < n; i++)
printf("%f\t", x[i]); printf("\nMaximum profit is:- %f", tp);
}
int main() {
float weight[20], profit[20], capacity; int num, i, j;
float ratio[20], temp;
printf("\nEnter the no. of objects:- "); scanf("%d", &num);
printf("\nEnter the wts and profits of each object:- "); for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i], &profit[i]);
}
printf("\nEnter the capacityacity of knapsack:- "); scanf("%f", &capacity);
for (i = 0; i < num; i++) { ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) { if (ratio[i] < ratio[j]) {
temp = ratio[j]; ratio[j] = ratio[i]; ratio[i] = temp;
temp = weight[j]; weight[j] = weight[i]; weight[i] = temp;
temp = profit[j]; profit[j] = profit[i]; profit[i] = temp;
}
}
}
knapsack(num, weight, profit, capacity); getch();
return(0);
}
OUTPUT:
Conclusion:
Thus the C program for solving Knapsack problem has been executed successfully.
Experiment No.7 Prim’s algorithm
Aim:- Program to implement prim’s algorithm using greedy method
Objective: Write a C program to find the minimum spanning tree to implement prim’s algorithm using greedy method
Algorithm:
// C Program to implement prim’s algorithm using greedy method
#include<stdio.h> #include<conio.h>
int n, cost[10][10];
void prim() {
int i, j, startVertex, endVertex;
int k, nr[10], temp, minimumCost = 0, tree[10][3];
/* For first smallest edge */ temp = cost[0][0];
for (i = 0; i < n; i++) { for (j = 0; j < n; j++) {
if (temp > cost[i][j]) {
temp = cost[i][j]; startVertex = i; endVertex = j;
}
}
}
/* Now we have fist smallest edge in graph */ tree[0][0] = startVertex;
tree[0][1] = endVertex; tree[0][2] = temp; minimumCost = temp;
/* Now we have to find min dis of each vertex from either startVertex or endVertex by initialising nr[] array
*/
for (i = 0; i < n; i++) {
if (cost[i][startVertex] < cost[i][endVertex]) nr[i] = startVertex;
else
nr[i] = endVertex;
}
/* To indicate visited vertex initialise nr[] for them to 100 */ nr[startVertex] = 100;
nr[endVertex] = 100;
/* Now find out remaining n-2 edges */ temp = 99;
for (i = 1; i < n - 1; i++) { for (j = 0; j < n; j++) {
if (nr[j] != 100 && cost[j][nr[j]] < temp) { temp = cost[j][nr[j]];
k = j;
}
}
/* Now i have got next vertex */ tree[i][0] = k;
tree[i][1] = nr[k]; tree[i][2] = cost[k][nr[k]];
minimumCost = minimumCost + cost[k][nr[k]]; nr[k] = 100;
/* Now find if k is nearest to any vertex than its previous near value */
for (j = 0; j < n; j++) {
if (nr[j] != 100 && cost[j][nr[j]] > cost[j][k]) nr[j] = k;
}
temp = 99;
}
/* Now i have the answer, just going to print it */ printf("\nThe min spanning tree is:- ");
for (i = 0; i < n - 1; i++) { for (j = 0; j < 3; j++)
printf("%d", tree[i][j]); printf("\n");
}
printf("\nMin cost : %d", minimumCost);
}
void main() { int i, j; clrscr();
printf("\nEnter the no. of vertices :"); scanf("%d", &n);
printf("\nEnter the costs of edges in matrix form :");
for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
printf("\nThe matrix is : "); for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { printf("%d\t", cost[i][j]);
}
printf("\n");
}
prim();
getch();
}
Output:
Time Complexities:- The time required by algorithm Prim is O(n²), where n is the number of vertices in the graph G.
Conclusion:- Thus the C program to find the minimum spanning tree using prim’s algorithm has executed successfully.
Experiment No.8 Kruskal’s algorithm
Aim:- Program to implement Kruskal’s algorithm using greedy method
Objective: Write a C program to find the minimum spanning tree to implement Kruskal’s algorithm using greedy method
Algorithm:
//Program to implement Kruskal’s Algorithm using Greedy method
#include<stdio.h> #include<conio.h> #include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9]; int find(int);
int uni(int,int); void main()
{
clrscr();
printf(“\n***** KRUSKAL’S ALGORITHM FOR MINIMUM SPANNING TREE (MST)
*****\n”);
printf(“\nImplementation of Kruskal’s algorithm\n”); printf(“\nEnter the No. of Vertices\n”); scanf(“%d”,&n);
printf(“\nEnter the Cost Adjacency Matrix\n”); for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%d”,&cost*i+*j+); if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf(“\n*** FINAL MST ***”);
printf(“\nThe Edges of Minimum Cost Spanning Tree are\n”); while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j]; a=u=i;
b=v=j;
}
}
}
u=find(u); v=find(v); if(uni(u,v))
{
printf(“\n%d Edge (%d,%d) = %d”,ne++,a,b,min); mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf(“\nMinimum Cost = %d\n”,mincost); getch();
}
int find(int i)
{
while(parent[i]) i=parent[i]; return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i; return 1;
}
return 0;
}
OUTPUT:
Time Complexities:- The computing time is O(|E| log |E|) where E is the edge set of graph G.
Conclusion:- Thus the C program to find the minimum spanning tree using Kruskal’s algorithm has executed successfully.
Experiment No.9
Graph Traversal: Breadth First Search
Aim:- Program to implement graph traversal using Breadth First Search
Objective: Write a C program to implement graph traversal using Breadth First Search
Theory:
BFS Breadth First Search is an algorithm used to search the Tree or Graph. BFS search starts from root node then traversal into next level of graph or tree and continues, if item found it stops otherwise it continues. The disadvantage of BFS is it requires more memory compare to Depth First Search (DFS).
Algorithm:
//Program for graph traversal using BFS//
#include<stdio.h> #include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1; void bfs(int v) {
for (i=1;i<=n;i++) if(a[v][i] && !visited[i]) q[++r]=i;
if(f<=r) {
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main() {
int v; clrscr();
printf("\n Enter the number of vertices:"); scanf("%d",&n);
for (i=1;i<=n;i++) { q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n"); for (i=1;i<=n;i++)
for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:"); scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n"); for (i=1;i<=n;i++)
if(visited[i]) printf("%d\t",i); else
printf("\n Bfs is not possible"); getch();
}
OUTPUT:
Time Complexities:- Let T(n,e) and S(n,e) be the maximum time and maximum additional space taken by algorithm BFS on any graph G with n vertices and e edges. T(n, e) = Θ(n + e) and S(n, e) = Θ(n) if G is represented by its adjacency lists. If G is represented by its adjacency matrix, then T(n, e) =Θ(n²) and S(n ,e) = Θ(n).
Conclusion:- Thus the C program for graph traversal using breadth first search has executed successfully
Experiment No.10
Graph Traversal: Depth First Search
Aim:- Program to implement graph traversal using Depth First Search
Objective: - Write a C program to implement graph traversal using Depth First Search
Theory:- DFS Depth First Search is an algorithm used to search the Tree or Graph. DFS search starts from root node then traversal into left child node and continues, if item found it stops otherwise it continues. The advantage of DFS is it requires less memory compare to Breadth First Search (BFS).
Algorithm:-
// Program for graph traversal using Depth First Search// #include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n; void dfs(int v) {
int i; reach[v]=1;
for (i=1;i<=n;i++) if(a[v][i] && !reach[i]) {
printf("\n %d->%d",v,i); dfs(i);
}
}
void main() {
int i,j,count=0; clrscr();
printf("\n Enter number of vertices:"); scanf("%d",&n);
for (i=1;i<=n;i++) {
reach[i]=0;
for (j=1;j<=n;j++) a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n"); for (i=1;i<=n;i++)
for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
dfs(1); printf("\n");
for (i=1;i<=n;i++) {
if(reach[i]) count++;
}
if(count==n)
printf("\n Graph is connected"); else printf("\n Graph is not connected"); getch();
OUTPUT:
Time Complexities:- Let T(n, e) and S(n, e) be the maximum time and maximum - additional space taken by algorithm DFS for an n-vertex and e-edge graph, then S(n, e)
= Θ(n) and T(n, e) = Θ(n + e) if adjacency lists are used and T(n, e) =Θ(n²) if adjacency matrices are used.
Conclusion:- Thus the C program for graph traversal using depth first search has executed successfully
Experiment No.11 N Queen’s problem
Aim:- Program to implement N queen’s problem
Objective: - Write a C program to solve N queen’s problem using Backtracking
Theory:- N Queen’s problem is the puzzle. Placing chess queens on a chessboard, so that No two queens attack each other. Backtracking is used to solve the problem.
The n-queens problem consists of placing n queens on an n x n checker board in such a way that they do not threaten each other, according to the rules of the game of chess. Every queen on a checker square can reach the other squares that are located on the same horizontal, vertical, and diagonal line. So there can be at most one queen at each horizontal line, at most one queen at each vertical line, and at most one queen at each of the 4n-2 diagonal lines. Furthermore, since we want to place as many queens as possible, namely exactly n queens, there must be exactly one queen at each horizontal line and at each vertical line. The concept behind backtracking algorithm which is used to solve this problem is to successively place the queens in columns. When it is impossible to place a queen in a column (it is on the same diagonal, row, or column as another token), the algorithm backtracks and adjusts a preceding queen
Algorithm:-
// C Program for N queen’s problem using Backtracking //
#include<stdio.h> #include<conio.h> #include<math.h> int a[30],count=0; int place(int pos) { int i;
for (i=1;i<pos;i++) {
if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos)))) return 0;
}
return 1;
}
void print_sol(int n) {
int i,j; count++;
printf("\n\nSolution #%d:\n",count); for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
if(a[i]==j) printf("Q\t"); else printf("*\t");
}
printf("\n");
}
}
void queen(int n) { int k=1; a[k]=0;
while(k!=0) {
a[k]=a[k]+1; while((a[k]<=n)&&!place(k))
a[k]++;
if(a[k]<=n) {
if(k==n) print_sol(n); else {
k++; a[k]=0;
}
} else k--;
}
}
void main() {
int i,n; clrscr();
printf("Enter the number of Queens\n"); scanf("%d",&n);
queen(n);
printf("\nTotal solutions=%d",count); getch();
}
OUTPUT:
Complexity:-
The power of the set of all possible solutions of the n queen’s problem is n! and the bounding function takes a linear amount of time to calculate, therefore the running time of the n queens problem is O(n!).
Conclusion:- Thus the C program to solve N queen’s problem using Backtracking has executed successfully
Experiment No.12 All Pairs shortest Path
Aim:- Program to implement all pairs shortest path
Objective: - Write a C program to find all pairs shortest path using Floyd’s algorithm
Theory:- Floyd’s algorithm is applicable to both directed and undirected graphs provided that they do not contain a cycle. It is convenient to record the lengths of shortest path in an n- by- n matrix D called the distance matrix. The element dij in the ith row and jth column of matrix indicates the shortest path from the ith vertex to jth vertex (1<=i, j<=n). The element in the ith row and jth column of the current matrix D(k-1) is replaced by the sum of elements in the same row i and kth column and in the same column j and the kth column if and only if the latter sum is smaller than its current value.
Algorithm:-
Algorithm Floyd(W[1..n,1..n])
//Implements Floyd’s algorithm for the all-pairs shortest paths problem
//Input: The weight matrix W of a graph
//Output: The distance matrix of shortest paths length
{
D ← W
for k←1 to n do
{
for i ← 1 to n do
{
for j ← 1 to n do
{
D[i,j] ← min (D[i, j], D[i, k]+D[k, j] )
}
}
}
return D
}
// All pairs Shortest path //
Program:
#include<stdio.h> #include<conio.h>
void floyd(int[10][10],int); int min(int,int);
void main()
{
int n,a[10][10],i,j;
printf("Enter the no.of nodes : "); scanf("%d",&n);
printf("\nEnter the cost adjacency matrix\n"); for(i=1;i<=n;i++)
for(j=1;j<=n;j++) scanf("%d",&a[i][j]); floyd(a,n);
getch();
}
void floyd(int a[10][10],int n)
{
int d[10][10],i,j,k; for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) d[i][j]=a[i][j];
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
printf("\nThe distance matrix is\n"); for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",d[i][j]);
}
printf("\n");
}
}
int min (int a,int b)
{
if(a<b) return a; else return b;
}
Output:
Complexity:- The time efficiency of Floyd’s algorithm is cubic i.e. Θ (n3)
Conclusion:- Thus the C program to find shortest path using Floyd’s algorithm has executed successfully
Comments
Post a Comment