I.K.
GUJRAL PUNJAB TECHNICAL UNIVERSITY
KAPURTHALA
COMPUTER SCIENCE ENGINEERING
DESIGN AND ANALYSIS OF ALGORITHM
BTCS405-18
Practical filefor DAA LAB
BTCS405-18
Submitted To: Submitted By:
Prag Sharma
[Link]
Rollno. :2438318
Department (Computer Science
B. Tech (CSE)
& Engineering)
Semester 4th (D)
CSE DEPARTMENT, I.K Gujral Punjab Technical University, Kapurthala
Subject Name: DAA Lab Subject Code: BTCS 405-18
Department: B. Tech CSE 4th Faculty Name: Ms. Naveen Dahiya
S. NO. Experiment Page No Signature
Code and analyze solutions to following problem with 2-4
1 given strategies:
i. Knap Sack using greedy approach
ii. Knap Sack using dynamic approach
Code and analyze to find an optimal solution to matrix 5
2 chain multiplication using dynamic programming.
Code and analyze to find an optimal solution to TSP
using dynamic programming. 6
3
Implementing an application of DFS such as:
i. to find the topological sort of a directed acyclic graph 7
ii. to find a path from source to goal in a maze.
4
Implement an application of BFS such as:
i. to find connected components of an undirected graph 8
ii. to check whether a given graph is bipartite.
5
Code and analyze to find shortest paths in a graph with
positive edge weights using Dijkstra’s algorithm. 9-10
6
Code and analyze to find shortest paths in a graph with
arbitrary edge weights using Bellman-Ford algorithm 11-12
7
Code and analyze to find shortest paths in a graph with 13-14
8 arbitrary edge weights using Floyd’s’ algorithm.
Code and analyze to find the minimum spanning tree in a 15-16
9 weighted, undirected graph using Prims’ algorithm
Code and analyze to find the minimum spanning tree in a 17-18
10 weighted, undirected graph using Kruskal’s’ algorithm.
Coding any real-world problem or TSP algorithm using 19
11 any heuristic technique.
Page | 1
Experiment- 1
Aim- Codeandanalyzesolutionstofollowingproblems with given strategies:
(i)
TheKnap Sack
selection usingthings,
of some greedyeachapproach:
with profit and weight values,tobe packedintoone ormore knapsacks
withcapacity is the fundamental idea behind all families of knapsack problems. The knapsack problem
had two versions that are as follows:
1. Fractional Knapsack Problem
2. 0 /1 Knapsack
Problem The fractional Knapsack
Problem using the Greedy Method is an efficient method to solve it, where you need to sort the items
according to their ratio of value/weight. In a fractional knapsack, we can break items to maximize the
knapsack's total value. This problem in which we can break an item is also called the Fractional
knapsack problem.
Program
#include <iostream>
using namespace std;
typedef struct {
int v;
int w;
float d;
} Item;
void input(Item items[],int sizeOfItems) {
cout << "Enter total "<< sizeOfItems <<" item's values and weight" <<
endl;
for(int i = 0; i < sizeOfItems; i++) {
cout << "Enter "<< i+1 << " V ";
cin >> items[i].v;
cout << "Enter "<< i+1 << " W ";
cin >> items[i].w;
}
}
void display(Item items[], int sizeOfItems) {
int i;
cout << "values: ";
for(i = 0; i < sizeOfItems; i++) {
cout << items[i].v << "\t";
}
cout << endl << "weight: ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].w << "\t";
}
cout << endl;
Page | 2
}
bool compare(Item i1, Item i2) {
return (i1.d > i2.d);
}
float knapsack(Item items[], int sizeOfItems, int W) {
int i, j;
float totalValue = 0, totalWeight = 0;
for (i = 0; i < sizeOfItems; i++) {
items[i].d = (float)items[i].v / items[i].w; //typecasting done (v is int and w is also int so we get final
value of d as int)
}
sort(items, items+sizeOfItems, compare);
for(i=0; i<sizeOfItems; i++) {
if(totalWeight + items[i].w<= W) {
totalValue += items[i].v ;
totalWeight += items[i].w;
} else {
int wt = W-totalWeight;
totalValue += (wt * items[i].d);
totalWeight += wt;
break;
}}
cout << "Total weight in bag " << totalWeight<<endl;
return totalValue;
}
int main() {
int W;
Item items[4];
input(items, 4);
cout << "Entered data \n";
display(items,4);
cout<< "Enter Knapsack weight \n";
cin >> W;
float mxVal = knapsack(items, 4, W);
cout << "Max value for "<< W <<" weight is "<< mxVal;
}
Output
Page | 3
(i) Knap Sack using dynamic approach : The Knapsack problem can also be solved using dynamic
programming, which guarantees an optimal solution. The dynamic programming approach involves
building a table of maximum possible values for all possible combinations of items and knapsack
capacities.
The dynamic programming approach to the Knapsack problem involves the following steps:
1. Create a 2D array dp of size (n+1) x (W+1), where n is the number of items and W is the capacity of
the knapsack.
2. Initialize the first row and column of dp to 0, since there are no items to choose from and the knapsack
has no capacity.
3. Fill in the table using a bottom-up approach. For each item i and each capacity j, calculate the
maximum value that can be obtained using the item and the remaining capacity. This can be done using
the formula dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]), where weight[i] and value[i] are the
weight and value of item i, respectively. The maximum value can either come from not including item i
or including item i and adding its value to the maximum value that can be obtained using the remaining
capacity j-weight[i].
4. Return the value in the last cell of dp, which represents the maximum possible value that can be
obtained using all items and the full capacity of the knapsack.
Program
#include <iostream>
using namespace std;
struct Item {
int value, weight;
Item(int value, int weight) : value(value), weight(weight) {}
};
int knapsackDP(int W, Item arr[], int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (arr[i - 1].weight <= j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i - 1].weight] + arr[i - 1].value);
}
else {
dp[i][j] = dp[i - 1][j];
}}}
return dp[n][W];
}
int main() {
int W = 50; // Knapsack capacity
Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; // Items (value, weight)
int n = sizeof(arr) / sizeof(arr[0]);
int maxVal = knapsackDP(W, arr, n);
cout << "Maximum value: " << maxVal << endl;
return 0;
}
Page | 4
Experiment- 2
Aim- Code and analyze to find an optimal sol to matrix chain multiplication using dynamic
programming:
It is a Method under Dynamic Programming in which previous output is taken as input for next. Here, Chain
means one matrix's column is equal to the second matrix's row [always].
In general:
If A = ⌊aij⌋ is a p x q
matrix B = ⌊bij⌋ is a q x r
matrix C = ⌊cij⌋ is a p x r
matrix.
Then
Program
#include <bits/stdc++.h>
using namespace std;
int MatrixChainOrder(int p[], int i, int j){
if (i == j)
return 0;
int k;
int mini = INT_MAX; int count;
for (k = i; k < j; k++){
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
mini = min(count, mini);
}
return mini;
}
int main(){
int arr[] = { 1, 2, 3, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, N - 1);
return 0;
}
Output
Page | 5
EXPERIMENT -3
AIM: CodeandanalyzetofindtheoptimalsolutionforTSPusing dynamic programming
Travelling Salesman Problem (TSP):
Given a set of cities and thedistance between everypair of cities, theproblem is to find
the shortest possible route that visits every city exactly once and returns to the starting
point. Note the difference
between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there
exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph
is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.
Program:
#include <iostream>
using namespace std;
const int n = 4; // there are four nodes in example graph (graph is 1-based)
const int MAX = 100000 int dist[n + 1][n + 1] = {
{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
}
int memo[n + 1][1 << (n + 1)];
int fun(int i, int mask){
if (mask == ((1 << i) | 3)) return dist[1][i];
if (memo[i][mask] != 0) return memo[i][mask]; int res = MAX;
for (int j = 1; j <= n; j++)
if ((mask & (1 << j)) && j != i && j != 1)
res = std::min(res, fun(j, mask & (~(1 << i))+ dist[j][i]); return memo[i][mask] = res;
}
int main(){
int ans = MAX;
for (int i = 1; i <= n; i++
ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);
printf("The cost of most efficient tour = %d", ans);
return 0;
}
OUTPUT:
Thecostofmost efficient tour = 80
Page | 6
EXPERIMENT - 4
AIM: Implementation of an application of DFS Such as:
i) To find the topological sort of directed graph
ii) Find path to source goal in maze
Depth First Traversal (or Search) for a graph is like Depth First Traversal of a tree. The only catch here is, that,
unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than
once, use a boolean visited array. A graph can have more than one DFS traversal.
Program:
#include <bits/stdc++.h>
using namespace std; class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;
void addEdge(int v, int w); void DFS(int v);
};
void Graph::addEdge(int v, int w){
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFS(int v){
visited[v] = true; cout << v << " "; list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i])
DFS(*i);
}
int main(){
Graph g; [Link](0, 1);
[Link](0, 2);
[Link](1, 2);
[Link](2, 0);
[Link](2, 3);
[Link](3, 3);
cout << "Following is Depth First Traversal" " (starting from vertex 2) \n";
[Link](2);
return 0;
}
Output:
Following is Depth First Traversal (starting from vertex 2)
2013
Page | 7
Experiment - 5
AIM: Implementation of an application of BFS Such as:
i. to find connected components of an undirected graph
ii. to check whether a graph is bipartite
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node
that satisfies a given property. It starts at the tree root and explores all nodes at the present
depth prior to moving on to the nodes at the next depth level. Extra memory, usually a
queue, is needed to keep track of the child nodes that were encountered but not yet explored.
Program:
#include <bits/stdc++.h>
using namespace std; class Graph {
int V;
vector<list<int> > adj;
public:
// Constructor Graph(int V);
void addEdge(int v, int w); void BFS(int s);
};
Graph::Graph(int V){
this->V = V; [Link](V);
}
void Graph::addEdge(int v, int w){
// Add w to v’s list.
adj[v].push_back(w);
}
void Graph::BFS(int s){
vector<bool> visited; [Link](V, false);
list<int> queue; visited[s] = true;
queue.push_back(s);
while (![Link]()) { s = [Link]();
cout << s << " "; queue.pop_front();
for (auto adjacent : adj[s]) {
if (!visited[adjacent]) { visited[adjacent] = true;
queue.push_back(adjacent);
}}}}
int main(){
Graph g(4); [Link](0, 1);
[Link](0, 2);
[Link](1, 2);
[Link](2, 0);
[Link](2, 3);
[Link](3, 3);
cout << "Following is Breadth First Traversal "<< "(starting from vertex 2): "; [Link](2);
return 0;
}
Output:
Followingis Breadth First Traversal (starting from vertex 2): 2 0 3 1
Page | 8
Experiment- 6
Aim: Code and analyze to find shortest path in a graph with positive edge weight s using
Dijkstra’s algorithm.
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree.
Like Prim’s MST, generate a SPT (shortest path tree) with a given source as a root.
Maintain two sets, one set contains vertices included in the shortest-path tree, other set
includes vertices not yet included in the shortest- path tree. At every step of the
algorithm, find a vertex that is in the other set (set not yet included) and has a
minimum distance from the source.
Program:
#include <iostream>
using namespace std;
#include <limits.h>
#define V
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 printSolution(int dist[]){
cout << "Vertex \t Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << " \t\t\t\t" << dist[i] << endl;
}
void dijkstra(int graph[V][V], int src){
int dist[V]; // The output array.
dist[i] will hold the bool sptSet[V]; // sptSet[i] will be true if vertex i is
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);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v]
&& dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
Page | 9
}
printSolution(dist);
}
int main(){
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
// Function call dijkstra(graph, 0);
return 0;
}
Output:
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
Page | 10
Experiment -7
Aim: Code and analyze to find shortest path in a graph with arbitrary edges weight
using Bellman-ford algorithm.
Given a graph and a source vertex src in the graph, find the shortest paths from src to all vertices in the given
graph. The graph may contain negative weight edges. Dijkstra’s algorithm is a Greedy algorithm and the time
complexity is O((V+E)LogV) (with the use of the Fibonacci heap). Dijkstra doesn’t work for Graphs with
negative weights, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites
well for distributed systems. But time complexity of Bellman-Ford is O(V * E), which is more than Dijkstra.
Program:
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int src, dest, weight;
};
struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
struct Edge* edge
};
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;
}
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]);
}
void BellmanFord(struct Graph* graph, int src){
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX; dist[src] = 0;
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;
}}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
Page | 11
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
}}
printArr(dist, V); return;
}
int main(){
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
Output:
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1
Page | 12
Experiment -8
Aim: Code and analyze to find shortest paths in a graph with arbitrary edge weights using
Flyods’ algorithm.
Flyods’ algorithm.:
Floyd-Warshall Algorithm is an algorithm for finding the shortest
path between all the pairs of vertices in a weighted graph. This
algorithm works for both the directed and undirected weighted
graphs. But, it does not work for the graphs with negative cycles
(where the sum of the edges in a cycle is negative)
Program:
#include<iostream>
#define NODE 7
#define INF 999
using namespace std;
int costMat[NODE][NODE] = {
{0, 3, 6, INF, INF, INF, INF},
{3, 0, 2, 1, INF, INF, INF},
{6, 2, 0, 1, 4, 2, INF},
{INF, 1, 1, 0, 2, INF, 4},
{INF, INF, 4, 2, 0, 2, 1},
{INF, INF, 2, INF, 2, 0, 1},
{INF, INF, INF, 4, 1, 1, 0}
};
void floydWarshal() {
int cost[NODE][NODE];
for(int i = 0; i<NODE; i++)
//defind to store shortest distance from any node to any node
for(int j = 0; j<NODE; j++)
cost[i][j] = costMat[i][j];
//copy costMatrix to new matrix
for(int k = 0; k<NODE; k++) { for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++) if(cost[i][k]
+cost[k][j] < cost[i][j])
cost[i][j] = cost[i][k]+cost[k][j];
}
cout << "The matrix:" << endl;
for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++) cout << setw(3) << cost[i][j];
cout << endl;
}
Page | 13
}
int main() {
floydWarshal();
}
Output:
Page | 14
Experiment -9
Aim: Code and analyze to find the minimum spanning tree in a weighted, undirected graph
using Prims’ algorithm.
Prim's algorithm :
Prim's algorithmis a greedy algorithm that is usedto find
the minimum spanning tree for a network. It is used to
connect every node together sing the smallest possible
total obtained when the edges are added together. For
example, Prim's algorithm has been used on the network
below to find the minimum spanning tree.
Program:
#include <bits/stdc++.h>
using namespace std;
#define V 5
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;
}
void printMST(int parent[], int graph[V][V]){
cout << "Edge \tWeight\n"; for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
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++) {
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];
}
Page | 15
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
Page | 16
Experiment -10
Aim: Code and analyze to find the minimum spanning tree in a weighted, undirected graph
using Kruskal’s’ algorithm.
Kruskals’ algorithm.:
Kruskal's algorithm is a greedy algorithm in graph theory that is used to findthe
Minimum spanning tree (A subgraph of a graph G ( V , E ) G(V,E) G(V,E) which is a
tree and includes all the vertices of the given graph such that the sum of the weight of
the edges is minimum) of a given connected, weighted, undirected .
Program:
#include <bits/stdc++.h>
using namespace std;
union class DSU {
int* parent;
int* rank;
public:
DSU(int n){
parent = new intt[r];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = -1;
rank[i] = 1;
}}
int find(int i){
if (parent[i] == -1)
return i;
return parent[i] = find(parent[i]);
}
void unite(int x, int y){
int s1 = find(x);
int s2 = find(y);
if (s1 != s2) {
if (rank[s1] < rank[s2]) {
parent[s1] = s2;
}
else if (rank[s1] > rank[s2]) {
parent[s2] = s1;
Page | 17
} else {
parent[s2] = s1;
rank[s1] += 1;
}}} };
class Graph {
vector<vector<int> > edgelist;
int V;
public:
Graph(int V) { this->V = V; }
void addEdge(int x, int y, int w){
edgelist.push_back({ w, x, y });
}
void kruskals_mst(){
sort([Link](), [Link]());
DSU s(V);
int ans = 0;
cout << "Following are the edges in the constructed MST"<< endl;
for (auto edge : edgelist) {
int w = edge[0];
int x = edge[1];
int y = edge[2];
if ([Link](x) != [Link](y)) { [Link](x, y);
ans += w;
cout << x << " -- " << y << " == " << w<< endl;
}}
cout << "Minimum Cost Spanning Tree: " << ans;
}};
Output
int main(){
Graph g(4);
[Link](0, 1, 10);
[Link](1, 3, 15);
[Link](2, 3, 4);
[Link](2, 0, 6)
[Link](0, 3, 5);
return 0;
}
Page | 18
Experiment -11
Aim: Coding any real-world problem or TSP algorithm using any heuristic technique.
Travelling salesman problem:
In thetravelingsalesman Problem, a salesman must visits n cities. We can
say that salesman wishes to make a tour or Hamiltonian cycle, visiting each
city exactly once and finishing at the city he starts from. There is a non-
negative cost c (i, j) to travel from the city i to city j. The goal is to find a
tour of minimum cost. We assume that every two cities are connected. Such
problems are called Traveling-salesman problem (TSP).
Program:
#include <bits/stdc++.h>
using namespace std;
#define V 4
int travllingSalesmanProblem(int graph[][V], int s){
for (int i = 0; i < V; i++) if (i != s)
vertex.push_back(i);
int min_path = INT_MAX;
do{
int current_pathweight = 0;
int k = s;
for (int i = 0; i < [Link](); i++) {
current_pathweight += graph[k][vertex[i]];
k =vertex[i];
}
current_pathweight += graph[k][s];
min_path = min(min_path, current_pathweight);
} while (next_permutation([Link](), [Link]()));
return min_path;
}
int main(){
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl; return 0;
}
Output:
Page | 19