Code:-
#include <stdio.h>
#include <stdlib.h> // For system()
int min(int, int);
int main() {
int v, i, j, k, adj[10][10];
// Clear screen
system("clear"); // Use "cls" for Windows
printf("\nEnter number of vertices: ");
scanf("%d", &v);
// Input adjacency matrix
for (i = 1; i <= v; i++) {
for (j = 1; j <= v; j++) {
if (i == j)
adj[i][j] = 0;
else {
printf("\nIf edge exists between %d and %d, enter weight: ", i, j);
scanf("%d", &adj[i][j]);
// Print initial adjacency matrix
printf("\nThe adjacency matrix is:\n");
for (i = 1; i <= v; i++) {
for (j = 1; j <= v; j++) {
printf("\t%d", adj[i][j]);
printf("\n");
// Apply Floyd-Warshall Algorithm
for (k = 1; k <= v; k++) {
for (i = 1; i <= v; i++) {
for (j = 1; j <= v; j++) {
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
// Print updated adjacency matrix after each step
printf("\nThe new adjacency matrix is:\n");
for (i = 1; i <= v; i++) {
for (j = 1; j <= v; j++) {
printf("\t%d", adj[i][j]);
printf("\n");
// Final adjacency matrix
printf("\nThe final adjacency matrix is:\n");
for (i = 1; i <= v; i++) {
for (j = 1; j <= v; j++) {
printf("\t%d", adj[i][j]);
printf("\n");
getchar(); // Wait for user input before exiting
return 0;
int min(int a, int b) {
return (a < b) ? a : b;
Output:-
Enter number of vertices: 3
If edge exists between 1 and 2, enter weight: 1
If edge exists between 1 and 3, enter weight: 8
If edge exists between 2 and 1, enter weight: 9
If edge exists between 2 and 3, enter weight: 5
If edge exists between 3 and 1, enter weight: 1
If edge exists between 3 and 2, enter weight: 7
The adjacency matrix is:
0 1 8
9 0 5
1 7 0
The new adjacency matrix is:
0 1 8
9 0 5
1 2 0
The new adjacency matrix is:
0 1 6
6 0 5
1 2 0
The final adjacency matrix is:
0 1 6
6 0 5
1 2 0
Code:-
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void reverse_string(char *str);
int main() {
int i, j, m, n, k;
int b[100][100], c[100][100];
char x[100], y[100];
char t[100];
// Clear screen
system("clear"); // Use "cls" for Windows
// Input strings
printf("\nEnter the first string: ");
fgets(x, sizeof(x), stdin);
x[strcspn(x, "\n")] = '\0'; // Remove newline character
printf("\nEnter the second string: ");
fgets(y, sizeof(y), stdin);
y[strcspn(y, "\n")] = '\0'; // Remove newline character
printf("\n1 is vertical, 0 is Horizontal, -1 is diagonal:\n");
m = strlen(x);
n = strlen(y);
// Initialize the matrices
for (i = 0; i <= m; i++) {
c[i][0] = 0;
for (j = 0; j <= n; j++) {
c[0][j] = 0;
// Fill matrices using LCS logic
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
if (x[i - 1] == y[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = -1; // Diagonal
} else if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
b[i][j] = 1; // Vertical
} else {
c[i][j] = c[i][j - 1];
b[i][j] = 0; // Horizontal
// Print the cost matrix
printf("\nThe cost is:\n");
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
printf("\t%d", c[i][j]);
printf("\n");
// Print the direction matrix
printf("\nThe direction is:\n");
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
printf("\t%d", b[i][j]);
printf("\n");
// Traceback to find the LCS
i = m;
j = n;
k = 0;
while (i > 0 && j > 0) {
if (b[i][j] == 1) {
i--;
} else if (b[i][j] == 0) {
j--;
} else {
t[k] = y[j - 1];
k++;
i--;
j--;
t[k] = '\0';
// Reverse the traced path
reverse_string(t);
printf("\nThe path is: %s", t);
printf("\nThe length is: %d\n", (int)strlen(t));
return 0;
// Function to reverse a string
void reverse_string(char *str) {
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
char temp = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = temp;
}
Output:-
