PRACTICAL NO: 9

Write a program to find shortest path from your home to college using Bellman-Ford
algorithm.

The Bellman–Ford algorithm is like a guide that helps you find the shortest path from one city to all
other cities, even if some roads have negative lengths. It’s like a GPS for computers, useful for figuring
out the quickest way to get from one point to another in a network. In this article, we’ll take a closer
look at how this algorithm works and why it’s so handy in solving everyday problems.

Algorithm:

1. Initialization:
o Set the distance to the source vertex d(source)=0d(source) = 0d(source)=0.
o Set the distance to all other vertices d(v)=∞d(v) = \inftyd(v)=∞ (infinity).
2. Relaxation:
o For each vertex vvv in the graph, do the following for V−1V-1V−1 iterations (where
VVV is the number of vertices):
 For each edge (u,v)(u, v)(u,v) with weight www:
 If d(u)+w<d(v)d(u) + w < d(v)d(u)+w<d(v):
 Update d(v)=d(u)+wd(v) = d(u) + wd(v)=d(u)+w.
3. Check for Negative Weight Cycles:
o For each edge (u,v)(u, v)(u,v) with weight www:
 If d(u)+w<d(v)d(u) + w < d(v)d(u)+w<d(v):
 A negative weight cycle exists, and you can report that.

Program:

// A C++ program for Bellman-Ford's single source

// shortest path algorithm.

#include <bits/stdc++.h>

using namespace std;

// a structure to represent a weighted edge in graph

struct Edge {

int src, dest, weight;

};

// a structure to represent a connected, directed and

// weighted graph

struct Graph {

// V-> Number of vertices, E-> Number of edges

int V, E;

// graph is represented as an array of edges.

struct Edge* edge;

};

// Creates a graph with V vertices and E edges

struct Graph* createGraph(int V, int E)

struct Graph* graph = new Graph;

graph->V = V;

graph->E = E;

graph->edge = new Edge[E];

return graph;

// A utility function used to print the solution

void printArr(int dist[], int n)

printf("Vertex Distance from Source\n");

for (int i = 0; i < n; ++i)

 printf("%d \t\t %d\n", i, dist[i]);

// The main function that finds shortest distances from src

// to all other vertices using Bellman-Ford algorithm. The

// function also detects negative weight cycle

void BellmanFord(struct Graph* graph, int src)

int V = graph->V;

int E = graph->E;

int dist[V];

// Step 1: Initialize distances from src to all other

// vertices as INFINITE

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

dist[i] = INT_MAX;

dist[src] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple

// shortest path from src to any other vertex can have

// at-most |V| - 1 edges

for (int i = 1; i <= V - 1; i++) {

for (int j = 0; j < E; j++) {

int u = graph->edge[j].src;
 int v = graph->edge[j].dest;

int weight = graph->edge[j].weight;

if (dist[u] != INT_MAX

&& dist[u] + weight < dist[v])

dist[v] = dist[u] + weight;

// Step 3: check for negative-weight cycles. The above

// step guarantees shortest distances if graph doesn't

// contain negative weight cycle. If we get a shorter

// path, then there is a cycle.

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

int u = graph->edge[i].src;

int v = graph->edge[i].dest;

int weight = graph->edge[i].weight;

if (dist[u] != INT_MAX

&& dist[u] + weight < dist[v]) {

printf("Graph contains negative weight cycle");

return; // If negative cycle is detected, simply

// return

}
 printArr(dist, V);

return;

// Driver's code

int main()

cout<<"URN:2203395\n\n";

/* Let us create the graph given in above example */

int V = 5; // Number of vertices in graph

int E = 8; // Number of edges in graph

struct Graph* graph = createGraph(V, E);

// add edge 0-1 (or A-B in above figure)

graph->edge[0].src = 0;

graph->edge[0].dest = 1;

graph->edge[0].weight = -1;

// add edge 0-2 (or A-C in above figure)

graph->edge[1].src = 0;

graph->edge[1].dest = 2;

graph->edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)

graph->edge[2].src = 1;

graph->edge[2].dest = 2;

graph->edge[2].weight = 3;

// add edge 1-3 (or B-D in above figure)

graph->edge[3].src = 1;

graph->edge[3].dest = 3;

graph->edge[3].weight = 2;

// add edge 1-4 (or B-E in above figure)

graph->edge[4].src = 1;

graph->edge[4].dest = 4;

graph->edge[4].weight = 2;

// add edge 3-2 (or D-C in above figure)

graph->edge[5].src = 3;

graph->edge[5].dest = 2;

graph->edge[5].weight = 5;

// add edge 3-1 (or D-B in above figure)

graph->edge[6].src = 3;

graph->edge[6].dest = 1;

graph->edge[6].weight = 1;
 // add edge 4-3 (or E-D in above figure)

graph->edge[7].src = 4;

graph->edge[7].dest = 3;

graph->edge[7].weight = -3;

// Function call

BellmanFord(graph, 0);

return 0;

}
 PRACTICAL NO: 10

Output:
 PRACTICAL NO: 10

Write a program to solve 0/1 knapsack using dynamic programming.

Here knapsack is like a container or a bag. Suppose we have given some items which have some weights
or profits. We have to put some items in the knapsack in such a way total value produces a maximum
profit.

Algorithm:

1. Initialization:
o Create a 2D array dp where dp[i][j] will hold the maximum value that can be attained
with the first i items and a maximum weight of j.
2. Base Case:
o If there are no items or the capacity is 0, then the maximum value is 0:
 dp[0][j] = 0 for all j
 dp[i][0] = 0 for all i
3. Filling the DP Table:
o For each item iii from 1 to nnn:
 For each capacity jjj from 1 to WWW:
 If the weight of the item w[i−1]w[i-1]w[i−1] is less than or equal to jjj:
 Consider two cases:
1. Including the item: dp[i-1][j - w[i-1]] + v[i-1]
2. Excluding the item: dp[i-1][j]
 Take the maximum of both cases:
 dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])
If the weight of the item w[i−1]w[i-1]w[i−1] is greater than jjj:
Exclude the item:
 dp[i][j] = dp[i-1][j]
Result:
The value at dp[n][W] will contain the maximum value that can be attained with n items and capacity W.

Program:

#include <iostream>

#include <vector>

using namespace std;

int knapsackRecursive(vector<int>& weight,

vector<int>& value, int W, int n)

{
 // Base case: no items left or capacity is 0

if (n == 0 || W == 0)

return 0;

// If weight of the nth item is more than knapsack

// capacity W, it cannot be included

if (weight[n - 1] > W)

return knapsackRecursive(weight, value, W, n - 1);

// Return the maximum of two cases: (1) nth item

// included (2) not included

return max(value[n - 1]

+ knapsackRecursive(weight, value,

W - weight[n - 1],

n - 1),

knapsackRecursive(weight, value, W, n - 1));

int main()

cout<<"URN:2203395\n\n";

// define a vector of weight

vector<int> weight = { 1, 2, 4, 5 };

cout << "Weight: ";

for (auto it = weight.begin(); it != weight.end(); ++it) {

cout << *it << " ";

 }

cout << endl; // Print a newline after the weight vector

// define a vector of value

vector<int> value = { 5, 4, 8, 6 };

cout << "Values: ";

for (auto it = value.begin(); it != value.end(); ++it) {

cout << *it << " ";

cout << endl;

// Knapsack capacity

int W = 5;

cout << "Capacity: " << W << endl;

cout << "Maximum value = "

<< knapsackRecursive(weight, value, W,

weight.size())

<< endl;

return 0;

}
 PRACTICAL NO: 11

Input Graph: 4

1 4

1 11 9 18

0 2 2 5 5 13 7

16

5 2 2
3 6

Output Graph:

5 2 2
0 3 6 7

Output:
 PRACTICAL NO: 11

Write a program to find the shortest path of the multistage graph using dynamic
programming.

A Multistage graph is a directed, weighted graph in which the nodes can be divided into a set of stages
such that all edges are from a stage to next stage only (In other words there is no edge between vertices
of same stage and from a vertex of current stage to previous stage).

Algorithm:

1. Initialization:
o Let d[i]d[i]d[i] be the minimum distance from the source to vertex iii.
o Set d[start]=0d[start] = 0d[start]=0 (the distance to the source vertex) and d[i]=∞d[i] =
\inftyd[i]=∞ for all other vertices.
2. Backward Calculation:
o Start from the second-to-last stage and move backwards to the first stage:
 For each vertex jjj in the current stage:
 Update the distances to its connected vertices in the next stage using:
d[j]=min⁡(d[j],cost(j,k)+d[k])d[j] = \min(d[j], \text{cost}(j, k) +
d[k])d[j]=min(d[j],cost(j,k)+d[k])
 Here, kkk are the vertices in the next stage that are reachable from jjj.
3. Result:
o The shortest path from the source to the destination is found in d[end]d[end]d[end].

Program:

#include<bits/stdc++.h>

using namespace std;

#define N 8

#define INF INT_MAX

// Returns shortest distance from 0 to

// N-1.

int shortestDist(int graph[N][N]) {

// dist[i] is going to store shortest

// distance from node i to node N-1.

int dist[N];

dist[N-1] = 0;

// Calculating shortest path for

// rest of the nodes

for (int i = N-2 ; i >= 0 ; i--)

// Initialize distance from i to

// destination (N-1)

dist[i] = INF;

// Check all nodes of next stages

// to find shortest distance from

// i to N-1.

for (int j = i ; j < N ; j++)

// Reject if no edge exists

if (graph[i][j] == INF)

continue;

// We apply equation to

// distance to target through j.

// and compare with minimum distance

// so far.
 dist[i] = min(dist[i], graph[i][j] + dist[j]);

return dist[0];

// Driver code

int main()

cout<<"URN:2203395\n\n";

int graph[N][N] =

{{INF, 1, 2, 5, INF, INF, INF, INF},

{INF, INF, INF, INF, 4, 11, INF, INF},

{INF, INF, INF, INF, 9, 5, 16, INF},

{INF, INF, INF, INF, INF, INF, 2, INF},

{INF, INF, INF, INF, INF, INF, INF, 18},

{INF, INF, INF, INF, INF, INF, INF, 13},

{INF, INF, INF, INF, INF, INF, INF, 2},

{INF, INF, INF, INF, INF, INF, INF, INF}};

cout <<"Shortest distance is: "<< shortestDist(graph);

return 0;

}
 PRACTICAL NO: 12

Graph:

10
0 3

5 1

1 2

Output:
 PRACTICAL NO: 12

Write a program to find minimum distance between different cities of your state using
FloydWarshall algorithm.

It is used to find the shortest paths between all pairs of nodes in a weighted graph. This algorithm is
highly efficient and can handle graphs with both positive and negative edge weights, making it a
versatile tool for solving a wide range of network and connectivity problems.

Algorithm:

1. Initialization:
o Create a distance matrix DDD such that:
 D[i][j]=w(i,j)D[i][j] = w(i, j)D[i][j]=w(i,j) if there is an edge from iii to jjj.
 D[i][j]=0D[i][j] = 0D[i][j]=0 if i=ji = ji=j (the distance from a vertex to itself).
 D[i][j]=∞D[i][j] = \inftyD[i][j]=∞ if there is no edge between iii and jjj.
2. Dynamic Programming Update:
o For each intermediate vertex kkk from 1 to VVV:
 For each source vertex iii from 1 to VVV:
 For each destination vertex jjj from 1 to VVV:
 Update the distance:
D[i][j]=min⁡(D[i][j],D[i][k]+D[k][j])D[i][j] = \min(D[i][j],
D[i][k] + D[k][j])D[i][j]=min(D[i][j],D[i][k]+D[k][j])
 This checks if the path from iii to jjj through kkk is shorter than the
currently known shortest path.
3. Result:
o The distance matrix DDD will contain the shortest path distances between every pair of
vertices.

Program:

#include <iostream>

#include <limits.h>

#include <vector>

#define INF INT_MAX

using namespace std;

void printSolution(const vector<vector<int>> &dist)

{

int V = dist.size();

cout << "The following matrix shows the shortest distances"

" between every pair of vertices:\n";

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

for (int j = 0; j < V; ++j)

if (dist[i][j] == INF)

cout << "INF"

<< "\t";

else

cout << dist[i][j] << "\t";

cout << endl;

void floydWarshall(vector<vector<int>> &graph)

int V = graph.size();

vector<vector<int>> dist = graph;

for (int k = 0; k < V; ++k)

 {

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

for (int j = 0; j < V; ++j)

if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])

dist[i][j] = dist[i][k] + dist[k][j];

printSolution(dist);

int main()

cout<<"URN:2203395\n\n";

vector<vector<int>> graph = {{0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF,
0}};

floydWarshall(graph);

return 0;

}
 PRACTICAL NO: 13

Output:

4 queen problem

8 queen problem
 PRACTICAL NO: 13

Write a program to find the solution to the 8 queen’s problem using the backtracking.

Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally

by trying different options and undoing them if they lead to a dead end. It is commonly used in
situations where you need to explore multiple possibilities to solve a problem, like searching for a path
in a maze or solving puzzles like Sudoku.

Algorithm:

1. Initialize the Board: Create an 8x8 chessboard (2D array) initialized to 0.

2. Define the Backtracking Function:
o This function will attempt to place queens row by row.
o If a queen can be placed in a column of a given row, place the queen and recursively
attempt to place queens in the next row.
o If all queens are placed successfully, store the solution.
o If placing a queen leads to a conflict, backtrack by removing the queen and trying the
next column.
3. Check Validity: Before placing a queen, check if it can be safely placed in the current column
and diagonals.
4. Output Solutions: After exploring all possibilities, output all valid configurations.

Program:

#include <iostream>

#include <vector>

using namespace std;

// Function to print the chessboard

void printBoard(const vector<vector<int>>& board) {

for (const auto& row : board) {

for (int col : row) {

cout << (col ? "Q " : ". ");

cout << endl;

}
 cout << endl;

// Function to check if it's safe to place a queen at board[row][col]

bool isSafe(const vector<vector<int>>& board, int row, int col) {

int n = board.size();

// Check this column on the upper side

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

if (board[i][col] == 1) return false;

// Check upper diagonal on the left side

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 1) return false;

// Check upper diagonal on the right side

for (int i = row, j = col; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 1) return false;

return true;

// Backtracking function to solve the N Queens problem

void solveNQueens(vector<vector<int>>& board, int row) {

int n = board.size();

if (row >= n) {

printBoard(board);

return;

for (int col = 0; col < n; col++) {

if (isSafe(board, row, col)) {

board[row][col] = 1; // Place the queen

solveNQueens(board, row + 1); // Recur to place the rest

board[row][col] = 0; // Backtrack

int main() {

cout<<"URN:2203395\n\n";

int n;

cout<<"Enter the number of queens: ";

cin>>n;

vector<vector<int>> board(n, vector<int>(n, 0)); // Create an n x n board

solveNQueens(board, 0);

return 0;

}
 PRACTICAL NO: 14

Output:
 PRACTICAL NO: 14

Write a program to solve subset sum problem using Backtracking.

Subset sum can also be thought of as a special case of the 0–1 Knapsack problem. For each item, there
are two possibilities:
 Include the current element in the subset and recur for the remaining elements with the remaining
Sum.
 Exclude the current element from the subset and recur for the remaining elements.

Algorithm:

1. Input:
o A list of integers (nums).
o A target sum (target).
2. Function subsetSum(nums, n, target):
o Parameters:
 nums: the list of integers.
 n: the number of elements in the list.
 target: the desired sum we want to achieve.
3. Base Cases:
o If target == 0:
 Return true (a subset with the given sum has been found).
o If n == 0 and target != 0:
 Return false (no elements left to consider, and target not met).
4. Recursive Cases:
o If the last element (nums[n - 1]) is greater than target:
 Call subsetSum(nums, n - 1, target) (ignore the last element).
o Otherwise:
 Check two scenarios:
1. Exclude the last element:
 Call subsetSum(nums, n - 1, target).
2. Include the last element:
 Call subsetSum(nums, n - 1, target - nums[n -
1]).
 Return the logical OR of both scenarios.
5. Output:
o If subsetSum returns true, print "Found a subset with the given sum".
o Otherwise, print "No subset with the given sum".

Program:

#include <iostream>

#include <vector>
using namespace std;

// Function to check if a subset with the given sum can be formed

bool subsetSum(const vector<int>& nums, int n, int target) {

// Base Cases

if (target == 0) return true; // Found a subset with the required sum

if (n == 0) return false; // No elements left to consider

// If the last element is greater than the target, ignore it

if (nums[n - 1] > target) {

return subsetSum(nums, n - 1, target);

// Check if we can form the sum by either including or excluding the last element

return subsetSum(nums, n - 1, target) ||

subsetSum(nums, n - 1, target - nums[n - 1]);

int main() {

cout<<"URN:2203395\n\n";

vector<int> nums = {3, 34, 4, 12, 5, 2};

int target = 9; // Target sum

int n = nums.size();

if (subsetSum(nums, n, target)) {

cout << "Found a subset with the given sum " << target << endl;
 } else {

cout << "No subset with the given sum " << target << endl;

return 0;

}
 PRACTICAL NO: 15

Graph:
1 3

5
0

2 4

Output:
 PRCATICAL NO: 15

Write a program to use a queue to store the node and mark it as 'visited' until all its
neighbours (vertices that are directly connected to it) are marked. Implement by using bfs
algorithm for a graph

Breadth-First Search (BFS) is an algorithm used to explore nodes and edges of a graph. It operates by
starting at a specified node (often called the "source") and exploring all of its neighbors at the present
depth prior to moving on to nodes at the next depth level. This makes BFS particularly useful for finding
the shortest path in an unweighted graph.

Algorithm:

1. Initialization:
o Create a queue and a boolean array to track visited nodes.
o Enqueue the starting node and mark it as visited.
2. BFS Loop:
o While the queue is not empty:
 Dequeue a node from the front of the queue.
 Process the node (e.g., print it or perform some operation).
 For each unvisited neighbor of the current node:
 Mark the neighbor as visited.
 Enqueue the neighbor.
3. End: The algorithm continues until all reachable nodes from the source node have been
processed.

Program:

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

// Function to perform BFS on the graph

void bfs(int start, const vector<vector<int>>& graph, vector<bool>& visited) {

queue<int> q; // Create a queue to store nodes

q.push(start); // Enqueue the starting node

visited[start] = true; // Mark it as visited

 while (!q.empty()) {

int node = q.front(); // Get the front node

q.pop(); // Dequeue it

cout << "Visited: " << node << endl; // Process the node

// Explore all adjacent nodes

for (int neighbor : graph[node]) {

if (!visited[neighbor]) { // If neighbor hasn't been visited

visited[neighbor] = true; // Mark it as visited

q.push(neighbor); // Enqueue the neighbor

int main() {

cout<<"URN:2203395\n\n";

int vertices = 6; // Number of vertices in the graph

vector<vector<int>> graph(vertices); // Adjacency list representation

graph[0] = {1, 2};

graph[1] = {0, 3, 4};

graph[2] = {0, 4};

graph[3] = {1, 5};

graph[4] = {1, 2};

graph[5] = {3};
 vector<bool> visited(vertices, false); // Track visited nodes

cout << "BFS starting from node 0:" << endl;

bfs(0, graph, visited); // Start BFS from node 0

return 0;

}
 PRACTICAL NO: 16

Graph:

Output:
 PRACTICAL NO: 16

Write a program to implement the dfs algorithm for a graph.

Depth-First Search (DFS) is an algorithm used to explore nodes and edges of a graph. It starts at a
selected node (often called the "source") and explores as far as possible along each branch before
backtracking. This makes DFS particularly useful for tasks such as pathfinding, topological sorting, and
solving puzzles.

Algorithm:

1. Initialization:

o Create a stack or use recursion to keep track of nodes to be explored.

o Create a boolean array to track visited nodes.
2. DFS Function:
o Mark the current node as visited and process it (e.g., print it).
o For each unvisited neighbor of the current node:
 Recursively call the DFS function on that neighbor.
3. End: The algorithm continues until all reachable nodes from the source node have been
processed.

Program:

#include <iostream>

#include <vector>

using namespace std;

// Function to perform DFS on the graph

void dfs(int node, const vector<vector<int>>& graph, vector<bool>& visited) {

visited[node] = true; // Mark the current node as visited

cout << "Visited: " << node << endl; // Process the node

// Explore all adjacent nodes

for (int neighbor : graph[node]) {

if (!visited[neighbor]) { // If neighbor hasn't been visited

dfs(neighbor, graph, visited); // Recur on the neighbor

 }

int main() {

cout<<"URN:2203395\n\n";

int vertices = 6; // Number of vertices in the graph

vector<vector<int>> graph(vertices); // Adjacency list representation

graph[0] = {1, 2};

graph[1] = {0, 3, 4};

graph[2] = {0, 4};

graph[3] = {1, 5};

graph[4] = {1, 2};

graph[5] = {3};

vector<bool> visited(vertices, false); // Track visited nodes

cout << "DFS starting from node 0:" << endl;

dfs(0, graph, visited); // Start DFS from node 0

return 0;