1

INDEX
S.No. Title Page Date Of Remarks
No. Submission
1. Program For Itera ve and 21/03/24
02 21/03/25
Recursive Binary Search
2. Program For Merge Sort 28/03/24
05 28/03/25

3. Program For Quick Sort 04/04/24

08 04/04/25

4. Program For Strassen’s 11/04/24

11 11/04/25
Matrix Mul plica on
5. Program For Op mal Merge 18/04/24
14 18/04/25
Pa erns
6. Program For Huffman Coding 25/04/24
17 25/04/25

7. Minimum Spanning Tree 02/05/24

21 02/05/25
Using Kruskal’s Algorithm
8. Minimum Spanning Tree 09/05/24
25 09/05/25
Using Prim’s Algorithm
9. Single Source Shortest Path 16/05/24
28 16/05/25
Algorithm
10. Program for Floyd Warshal 30/05/24
31 30/05/25
Algorithm
11. Program for Travelling 06/06/24
34 06/06/25
Salesman Problem
12. Program for Hamiltonian 13/06/24
36 13/06/25
Cycle Problem
 2

Program 1
Itera ve and Recursive Binary Search Algorithm
Searching is an algorithm for finding an item with specified proper es among a
collec on of items. The Binary search requires an ordered list of elements and is
only applicable to the arrays. A binary search or half-interval search algorithm
locates the posi on of an item in a sorted array. Binary search works by comparing
an input value to the middle element of the array. The comparison determines
whether the element equals the input, less than the input or greater. When the
element being compared to equals the input the search stops and typically
returns the posi on of the element.

Itera ve Algorithm
An itera ve method a empts to solve a problem (for example, finding the root
of an equa on or system of equa ons) by finding successive approxima ons to
the solu on star ng from an ini al guess. This approach is in contrast to direct
methods, which a empt to solve the problem by a finite sequence of opera ons,
and, in the absence of rounding errors, would deliver an exact solu on.

Example: Find 103 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.

Step 1 (middle element is 19 < 103): -1 5 6 18 19 25 46 78 102 114

Step 2 (middle element is 78 < 103): -1 5 6 18 19 25 46 78 102 114

Step 3 (middle element is 102 < 103): -1 5 6 18 19 25 46 78 102 114

Step 4 (middle element is 114 > 103): -1 5 6 18 19 25 46 78 102 114

Step 5 (searched value is absent): -1 5 6 18 19 25 46 78 102 114

Complexity:
The Complexity of Itera ve Binary Search algorithm is O (log2n) where n is the
number of elements in the array.
 3
IMPLEMENTATION:
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
prin ("Not found");
else
prin ("Element is found at index %d", result);
return 0;
}
Output :
Element is found at index 1
 4
Recursive Algorithm
In recursive binary search algorithm, the list of elements is divided into two equal
sized half and then searching begins recursively in only one half of the list where
possibility of element to be present.

Complexity: The Complexity of Recursive Binary Search algorithm is O (log2n)

where n is the number of elements in the array.

IMPLEMENTATION :
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low)
if (array[mid] == x) return mid;
if (array[mid] > x) return binarySearch(array, x, low, mid - 1);
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
int main() {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1) prin ("Not found");
else prin ("Element is found at index %d", result);
}
Output :
Element is found at index 1
 5

Program- 2
Merge Sort Algorithm

The Mergesort algorithm is based on divide and conquer strategy. First, the
sequence to be sorted is decomposed into two halves (Divide). Each half is sorted
independently (Conquer). Then the two sorted halves are merged to a sorted
sequence (Combine).

Fig 3.1: Merge sort

The procedure mergesort sorts a sequence from index “low” to index “high”. First,
index “mid” in the middle between “low” and “high” is determined. Then the first
part of the sequence (from low to mid) and the second part (from mid+1 to high)
are sorted by recursive calls of mergesort. Then the two sorted halves are merged
by procedure merge. Recursion ends when low = high, i.e. when a subsequence
consists of only one element.
Complexity: The me complexity of Mergesort is O (n log2n).

IMPLEMENTATION:
#include <stdio.h>
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
 6
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++) L[i] = arr[p + i];
for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j];
int i=0, j=0, k=p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
 7
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted subarrays

merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
prin (" %d,", arr[i]);
prin ("\n");
}
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
prin ("Sorted array: \n");
printArray(arr, size);
}
Output :
1, 5, 6, 9, 10, 12
 8

Program- 3
Quick Sort Algorithm

Quicksort is a divide-and-conquer sor ng algorithm in which division is

dynamically carried out (as opposed to sta c division in Mergesort). The three
steps of Quicksort are as follows:
Divide: Rearrange the elements and split the array into two subarrays and an
element in between such that so that each element in the le subarray is less
than or equal the middle element and each element in the right subarray is
greater than the middle element.
Conquer: Recursively sort the two subarrays.

Example:
Sort the numbers: 65, 70, 75, 80, 85, 60, 55, 50, 45

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i j

65 70 75 80 85 60 55 50 45 +∞ 2 9
65 45 75 80 85 60 55 50 70 +∞ 3 8
65 45 50 80 85 60 55 75 70 +∞ 4 7
65 45 50 55 85 60 80 75 70 +∞ 5 6
65 45 50 55 60 85 80 75 70 +∞ 6 5
60 45 50 55 65 85 80 75 70 +∞

Complexity: O (nlogn)
 9
IMPLEMENTATION:
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int par on(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++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = par on(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
void printArray(int array[], int size) {
 10
for (int i = 0; i < size; ++i) {
prin (" %d,"array[i]);
}
prin ("\n");
}
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
quickSort(data, 0, n - 1);
printArray(data, n);
return 0;
}
Output :
0, 1, 2, 6, 7, 8, 9
 11

Program- 4
Strassen’s Matrix Mul plica on

Let A, B be two square matrices of size n X n. We want to calculate the matrix

product C as:

With

Then

The Strassen’s Matrix Mul plica on Algorithm for this is as follows:

Algorithm StressenMatMul ( *A, *B, *R, n)
{
if (n == 1) (*R) += (*A) * (*B);
else
{ matmul(A, B, R, n/4);
matmul(A, B+(n/4), R+(n/4), n/4);
matmul(A+2*(n/4), B, R+2*(n/4), n/4);
matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4);
matmul(A+(n/4), B+2*(n/4), R, n/4);
matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4);
 12
matmul(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4);
matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4);
}
}
Complexity :
Strassen’s algorithm is a Divide-and-Conquer algorithm that is asympto cally
faster than tradi onal approach, i.e. O(nlg7)=O(n2.81)

IMPLEMENTATION:
#include<stdio.h>
int main(){
int z[2][2];
int i, j;
int m1, m2, m3, m4 , m5, m6, m7;
int x[2][2] = {
{12, 34},
{22, 10}
};
int y[2][2] = {
{3, 4},
{2, 1}
};
prin ("The first matrix is: ");
for(i = 0; i < 2; i++) {
prin ("\n");
for(j = 0; j < 2; j++)
prin ("%d\t", x[i][j]);
}
prin ("\nThe second matrix is: ");
}
m1= (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]);
m2= (x[1][0] + x[1][1]) * y[0][0];
m3= x[0][0] * (y[0][1] - y[1][1]);
m4= x[1][1] * (y[1][0] - y[0][0]);
 13
m5= (x[0][0] + x[0][1]) * y[1][1];
m6= (x[1][0] - x[0][0]) * (y[0][0]+y[0][1]);
m7= (x[0][1] - x[1][1]) * (y[1][0]+y[1][1]);
z[0][0] = m1 + m4- m5 + m7;
z[0][1] = m3 + m5;
z[1][0] = m2 + m4;
z[1][1] = m1 - m2 + m3 + m6;
prin ("\nProduct achieved using Strassen's algorithm: ");
for(i = 0; i < 2 ; i++) {
prin ("\n");
for(j = 0; j < 2; j++)
prin ("%d\t", z[i][j]);
}
return 0;
}

Output :
The first matrix is:
12 34
22 10
The second matrix is:
3 4
2 1
Product achieved using Strassen's algorithm:
104 82
86 98
 14

Program- 5
Op mal Merge Pa erns

Given n sorted files, there are many ways in which to pair-wise merge them into
a single sorted file. Thus the op mal way to pair-wise merge n sorted files can be
performed using greedy method. Greedy a empt to obtain an op mal merge
pa ern is easy to formulate. Since merging an n-record file and m-record file
requires possibly n+m record moves, the obvious choice for selec on criteria is:
at each step merge the two smallest size files together.

For Example: Suppose there are 3 sorted lists L1, L2, and L3, of sizes 30, 20, and
10, respec vely, which need to be merged into a combined sorted list, but we can
merge only two at a me. We intend to find an op mal merge pa ern which
minimizes the total number of comparisons. For example, we can merge L1 and
L2, which uses 30 + 20 = 50 comparisons resul ng in a list of size 50. We can then
merge this list with list L3, using another 50 + 10 = 60 comparisons, so the total
number of comparisons is 50 + 60 = 110. Alterna vely, we can merge lists L2 and
L3, using 20 + 10 = 30 comparisons, the resul ng list (size 30) can then be merged
with list L1, for another 30 + 30 = 60 comparisons. So the total number of
comparisons is 30 + 60 = 90. It doesn’t take long to see that this la er merge
pa ern is the op mal one.

Binary Merge Trees: We can depict the merge pa erns using a binary tree, built
from the leaf nodes (the ini al lists) towards the root in which each merge of two
nodes creates a parent node whose size is the sum of the sizes of the two children.

Example of the op mal merge tree algorithm:

Here external nodes (leaf nodes or basic files) are represented by square and
internal nodes are represented by circle.
 15

Ini ally, 5 leaf nodes

2 3 5 7 9
with sizes
5
Itera on 1: merge 2
2 3 5 7 9
1 and 3 into 5
5 0 5 1 Itera on 2: merge 7 and
2 3 76 9 9 (chosen among 7, 9,
2 and 10) into 16
1 6 1
Itera on 3: merge 10 and 16
5 0 5 76 9
2 3
into 26

Cost = 2*3 + 3*3 + 5*2 + 7*2 + 9*2 = 57.

Fig : Construc on of op mal merge tree

IMPLEMENTATION:
#include <stdio.h>
#include <stdlib.h>
int op malMerge(int files[], int n)
{
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (files[j] > files[j + 1]) {
int temp = files[j];
files[j] = files[j + 1];
files[j + 1] = temp;
}
}
}
int cost = 0;
while (n > 1) {
int mergedFileSize = files[0] + files[1];
 16
cost += mergedFileSize;

files[0] = mergedFileSize;
for (int i = 1; i < n - 1; i++) {
files[i] = files[i + 1];
}
n--;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (files[j] > files[j + 1]) {
int temp = files[j];
files[j] = files[j + 1];
files[j + 1] = temp;
}
}
}
}
return cost;
}
int main()
{
int files[] = {5, 10, 20, 30, 30};
int n = sizeof(files) / sizeof(files[0]);
int minCost = op malMerge(files, n);
prin ("Minimum cost of merging is: %d Comparisons\n", minCost);
return 0;
}

Output :
Minimum cost of merging is: 205 Comparisons
 17
Program- 6
Huffman Coding

Huffman's scheme uses a table of frequency of occurrence for each symbol (or
character) in the input. This table may be derived from the input itself or from
data which is representa ve of the input. For instance, the frequency of
occurrence of le ers in normal English might be derived from processing a large
number of text documents and then used for encoding all text documents. We
then need to assign a variable-length bit string to each character that
unambiguously represents that character. This means that the encoding for each
character must have a unique prefix. If the characters to be encoded are arranged
in a binary tree:
An encoding for each character is found by following the tree from the route to
the character in the leaf: the encoding is the string of symbols on each branch
followed.
For example:
String Encoding
TEA 10 00 010
SEA 011 00 010
TEN 10 00 110

Fig 8.1: Huffman tree

IMPLEMENTATION:
#include <stdio.h>
#include <stdlib.h>
 18
#define MAX_TREE_HT 50
struct MinHNode {
char item;
unsigned freq;
struct MinHNode *le , *right;
};
struct MinHeap {
unsigned size;
unsigned capacity;
struct MinHNode **array;
};
}
// Min Heap Opera onal Func on Defini ons not given to be precise

struct MinHNode *buildHuffmanTree(char item[], int freq[], int size) {

struct MinHNode *le , *right, *top;
struct MinHeap *minHeap = createAndBuildMinHeap(item, freq, size);
while (!checkSizeOne(minHeap)) {
le = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', le ->freq + right->freq);
top->le = le ;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
 19
void printHCodes(struct MinHNode *root, int arr[], int top) {
if (root->le ) {
arr[top] = 0;
printHCodes(root->le , arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printHCodes(root->right, arr, top + 1);
}
if (isLeaf(root)) {
prin (" %c | ", root->item);
printArray(arr, top);
}
}
void HuffmanCodes(char item[], int freq[], int size) {
struct MinHNode *root = buildHuffmanTree(item, freq, size);
int arr[MAX_TREE_HT], top = 0;
printHCodes(root, arr, top);
}
void printArray(int arr[], int n) {
int i;
for (i = 0; i < n; ++i) prin ("%d", arr[i]);
prin ("\n");
}
int main() {
char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = { 5, 9, 12, 13, 16, 45};
 20
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
Output :
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
 21

Program- 7
Minimum Spanning Trees using Kruskal’s algorithm

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning

tree for a connected weighted graph. This means it finds a subset of the edges
that forms a tree that includes every vertex, where the total weight of all the
edges in the tree is minimized. If the graph is not connected, then it finds a
minimum spanning forest (a minimum spanning tree for each connected
component). Kruskal's algorithm is an example of a greedy algorithm.
Example:

Itera on Edge Components

0 - {1}; {2}; {3}; {4}; {5}; {6}; {7}

1 {1,2} {1,2}; {3}; {4}; {5}; {6}; {7}

2 {2,3} {1,2,3}; {4}; {5}; {6}; {7}

3 {4,5} {1,2,3}; {4,5}; {6}; {7}

4 {6,7} {1,2,3}; {4,5}; {6,7}

5 {1,4} {1,2,3,4,5}; {6,7}

6 {2,5} Not included (adds cycle)

7 {4,7} {1,2,3,4,5,6,7}
 22
The Minimum Spanning Tree will be:

Fig 9.2: Minimum Spanning Tree

IMPLEMENTATION:
#include <stdio.h>
#include <stdlib.h>
int comparator(const void* p1, const void* p2)
{
const int(*x)[3] = p1;
const int(*y)[3] = p2;
return (*x)[2] - (*y)[2];
}
void makeSet(int parent[], int rank[], int n)
{
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
 23
int findParent(int parent[], int component)
{
if (parent[component] == component) return component;
return parent[component] = findParent(parent, parent[component]);
}
void unionSet(int u, int v, int parent[], int rank[], int n)
{
u = findParent(parent, u);
v = findParent(parent, v);
if (rank[u] < rank[v]) parent[u] = v;
else if (rank[u] > rank[v]) parent[v] = u;
else parent[v] = u;
rank[u]++;
}
}
void kruskalAlgo(int n, int edge[n][3])
{
qsort(edge, n, sizeof(edge[0]), comparator);
int parent[n];
int rank[n];
int minCost = 0;
prin ("Following are the edges in the constructed MST\n");
for (int i = 0; i < n; i++) {
int v1 = findParent(parent, edge[i][0]);
int v2 = findParent(parent, edge[i][1]);
int wt = edge[i][2];
 24
if (v1 != v2) {
unionSet(v1, v2, parent, rank, n);
minCost += wt;
prin ("%d -- %d == %d\n", edge[i][0],
edge[i][1], wt);
}
}
prin ("Minimum Cost Spanning Tree: %d\n", minCost);
}
int main()
{
int edge[5][3] = { { 0, 1, 10 },
{ 0, 2, 6 },
{ 0, 3, 5 },
{ 1, 3, 15 },
{ 2, 3, 4 } };
kruskalAlgo(5, edge);
return 0;
}
Output :
Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19
 25

Program- 8
Minimum Spanning Trees using Prim’s algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a
connected weighted undirected graph. This means it finds a subset of the edges
that forms a tree that includes every vertex, where the total weight of all the
edges in the tree is minimized. The algorithm con nuously increases the size of a
tree, one edge at a me, star ng with a tree consis ng of a single vertex, un l it
spans all ver ces.
Example:

Complexity : O(V2)
IMPLEMENTATION :
 26
#include <stdio.h>
int minKey(int key[], bool mstSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
{
if (mstSet[v] == false && key[v] < min) min = key[v], min_index = v;
}
return min_index;
}
int printMST(int parent[], int graph[V][V])
{
prin ("Edge \tWeight\n");
for (int i = 1; i < V; i++)
prin ("%d - %d \t%d \n", parent[i], i,graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
 27
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++){
if (graph[u][v] && mstSet[v] == false&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
}
printMST(parent, graph);
}
int main()
{ int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
primMST(graph);
return 0;
}
Output :
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
 28

Program- 9
Single Source Shortest Path Algorithm
[Dijkstra’s Algorithm]

For a given source vertex (node) in the graph, the Dijkstra's algorithm finds the
path with lowest cost (i.e. the shortest path) between that vertex and every other
vertex. It can also be used for finding costs of shortest paths from a single vertex
to a single des na on vertex by stopping the algorithm once the shortest path to
the des na on vertex has been determined. For example, if the ver ces of the
graph represent ci es and edge path costs represent driving distances between
pairs of ci es connected by a direct road, Dijkstra's algorithm can be used to find
the shortest route between one city and all other ci es.

The basic formula for finding the distance is: D[i]= min(D[i], min j S(D[j]+C[j,i]))
Example: Consider the digraph

Complexity: The complexity of the algorithm is O (n2).

 29
IMPLEMENTATION :
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v;
}
return min_index;
}
void printSolu on(int dist[])
{
prin ("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++) prin ("%d \t\t\t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
for (int v = 0; v < V; v++){
 30
if(!sptSet[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u][v]<
dist[v]) dist[v] = dist[u] + graph[u][v];
}
printSolu on(dist);
}
int main()
{
int graph[V][V] = { { 0, 4, 0, 0},
{ 4, 0, 8, 0},
{ 0, 8, 0, 7},
{ 0, 0, 7, 0 }};

dijkstra(graph, 0);
return 0;
}
Output :
Vertex Distance from Source
0 0
1 4
2 12
3 19
 31

Program-10
Floyd-Warshal Algorithm using Dynamic Programming

The Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest

paths in a weighted graph (with posi ve or nega ve edge weights). A single
execu on of the algorithm will find the lengths (summed weights) of the shortest
paths between all pairs of ver ces though it does not return details of the paths
themselves. The Floyd-Warshall Algorithm is an applica on of Dynamic
Programming. Let dist(k,i,j) be the the length of the shortest path from i and j
that uses only the ver ces as intermediate ver ces. The following
recurrence:

 k = 0 is our base case - dist(0,i,j) is the length of the edge from vertex i to vertex
j if it exists, and otherwise.
 dist(k,i,j) = min(dist(k - 1,i,k) + dist(k - 1,k,j),dist(k - 1,i,j)): For any vertex i and
vertex j, the length of the shortest path from i to j with all intermediate ver ces
simply does not involve the vertex k at all (in which case it is the same as
dist(k - 1,i,j)), or that the shorter path goes through vertex k, so the shortest path
between vertex i and vertex j is the combina on of the path from vertex i to k,
and from vertex k to j.

Example: Consider the graph

Solu on:
 32
Complexity: Θ(n3)

IMPLEMENTATION :
#include <stdio.h>
#define V 4
#define INF 99999
void printSolu on(int dist[][V]);
void floydWarshall(int dist[][V])
{
int i, j, k;
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolu on(dist);
}
void printSolu on(int dist[][V]){
prin ("The following matrix shows the shortest distances between every pair
of ver ces \n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) prin ("%7s", "INF");
else prin ("%7d", dist[i][j]);
}
prin ("\n");
 33
}
}
int main()
{
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };
floydWarshall(graph);
return 0;
}
Output :
The following matrix shows the shortest distances between every pair of
ver ces
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
 34

Program- 11
Travelling Salesman Problem

Given a set of ci es and the distance between every pair of ci es, the problem is
to find the shortest possible route that visits every city exactly once and returns
to the star ng point.
For example, consider the graph shown in the figure on the right side. A TSP tour
in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The
problem is a famous NP-hard problem. There is no polynomial- me know
solu on for this problem.

Complexity : O(n2*2n)
IMPLEMENTATION :
#include <stdio.h>
#include <limits.h>
#define MAX_N 15 // Maximum number of ci es
int n;
int cost[MAX_N][MAX_N]; // Cost matrix
int dp[1 << MAX_N][MAX_N]; // Dynamic programming table
int tsp(int mask, int pos) {
if (mask == (1 << n) - 1) return cost[pos][0]; // Return to the star ng city
if (dp[mask][pos] != -1) return dp[mask][pos];
int ans = INT_MAX;
 35
for (int next = 0; next < n; next++) {
if ((mask & (1 << next)) == 0) { // If city 'next' is not visited
int newCost = cost[pos][next] + tsp(mask | (1 << next), next);
ans = min(ans, newCost);
}
}
return dp[mask][pos] = ans;
}
int main() {
prin ("Enter the number of ci es: ");
scanf("%d", &n);
prin ("Enter the cost matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) scanf("%d", &cost[i][j]);
}
memset(dp, -1, sizeof(dp));
int minCost = tsp(1, 0); // Start from city 0
prin ("Minimum cost of the TSP: %d\n", minCost);
return 0;
}
Output:
Enter the number of ci es: 3
Enter the cost matrix:
07
30
Minimum Cost of the TSP : 10
 36

Program- 12
Hamiltonian Cycle Problem

Hamiltonian Cycle or Circuit in a graph G is a cycle that visits every vertex

of G exactly once and returns to the star ng vertex. Finding a Hamiltonian Cycle
in a graph is a well-known NP-complete problem. Given an undirected graph, the
task is to determine whether the graph contains a Hamiltonian cycle or not. If it
contains, then prints the path.
Example : Input graph[][] = {{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1,
0, 0, 1},{0, 1, 1, 1, 0}}

Output: {0, 1, 2, 4, 3, 0}

Complexity : O(N!)

IMPLEMENTATION :
#include<stdio.h>
#define V 5
int isSafe(int v, int graph[V][V], int path[], int pos)
{
if (graph [ path[pos-1] ][ v ] == 0) return 0;
for (int i = 0; i < pos; i++) if (path[i] == v) return 0;
return 1;
 37
}
int hamCycleU l(int graph[V][V], int path[], int pos)
{
if (pos == V)
{
if ( graph[ path[pos-1] ][ path[0] ] == 1 ) return 1;
else return 0;
}
for (int v = 1; v < V; v++)
{
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
if (hamCycleU l (graph, path, pos+1) == 1) return 1;
path[pos] = -1;
}
}
return 0;
}
int hamCycle(int graph[V][V])
{
int path[V];
for (int i = 0; i < V; i++) path[i] = -1;
path[0] = 0;
if ( hamCycleU l(graph, path, 1) == 0 )
{
prin ("\nSolu on does not exist");
 38
return 0;
}
printSolu on(path);
return 1;
}
void printSolu on(int path[])
{
prin ("Solu on Exists, following is one Hamiltonian Cycle : \n");
for (int i = 0; i < V; i++) prin (" %d ", path[i]);
prin (" %d ", path[0]);
prin ("\n");
}
int main()
{
int graph1[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
hamCycle(graph1);
return 0;
}
Output :
Solu on Exists, following is one Hamiltonian Cycle :
012430