Question

Problem 3 (25 points) Write a program to find minimum weight cycle in an undirected weighted graph. The input is the Adjacency Matrix A of the graph. If there is an edge between vertex i to vertex j, and weight of this edge is u, then ?3] Aj, i-w. If there is no edge between i and J, A 11.j-Aj, i--1.

In C++

Answer 1

Solution C+ Code: //header file //for cin and cout using namespace std; //define the infinity value # define INFVALUE 0x3f3f3f3f //structure for edge data struct edgeDetail //declare required variable int sv; int dv; int weight; //class for undirected udGraph class udGraph int vertex; //declare the adjacent in list list <pair <int, int>>A; //for stores the data of every edge vector <edgeDetail> ed; public: //constructor for udGraph udGraph(int vertex) this->vertex vertex; A= new list <pairint , int>2Lve r tex];

//function declaration veid insertEdge (int sv, int dv, int w); veid deleteEdge (int sv, int dv, int w); intcomputeMinimumPath (int sv, int dv); veid deleteEdge (int sv, int dv); int coputeMinimumCycle ); //function definition for insert edge into given graph veid udGraph :: insertEdge (int sv, int dv, int w1) //push back Alsv] push back(make pair(dv, wl)); A[dv] push_back(make_pair (sv, wl)); //insert edge to given edge list edgeDetail el sv, dv, wl); ed.push_back (e1); //function definition for delete edge from given graph void udGraph :: deleteEdge (int sv, int dv, int w1) //for delete edge A[sv].remove (make_pair(dv, wl)); A[dv]. emove (make_pair(sv, wl)); //function definition for compute minimum path //using Dijikstra' s shortest path algorithm int udGraph:: computeMinimumPath (int sv, int dv) set pair<int, int>> s; //generate a vector for distances //initializes the infinity for every distance vector<int> d(vertex, INEVALUE) //insert the source itself sainsertmake_pair (0, sv)) while (!s.empty)) pairint, înt> t "(з.be gin()); =

2.era els.begin ( ) ); int sv t.second; list< pair<int, int> >::iterator it; far (ít =A[sv] .beg i n ( ) ; it !=A[3v].end ( ); ++1t) ant dv (*it) . first ; int weight - (it) second; //If there is minimum path to dv by su, then f (d[dv] > d[Isv] weight) ///check below condition 2.eraes (2. &And (make-pair (d [dv] , dv) ) ) ; //altering the distance of dv aldv] = d[sv] weight ; s.insert(make_pair(d[dv], dv)) //return shortest path return d[dv] i //function definition for find minimum weighted cycle int udGraph computeMinimumCycle( //for minimum cycle int mc = INT MAX ; //size int te = ed.size();

for (int r F 0r<te r++) //existing Edge data edgeDetail e= ed [r]; //call deleteEdge ) function deleteEge e.s, ey, e.weight); //compute minimum distance between 2 vertices int d computeMinimumPath (e. sv, e.dy); / /compute minimum cycle value mc = mín (mc, md + e.weight ); //call insertEd insertEdge(e.sv, e.av, e.weight ); ge return mc /main function int main() ant totalve rt ex 9; //create object for given undirected graph class udGraph udGraph adi (totalVert //create graph adiinstEdge(o, 1, 1); adiinstEdge(0, 2, 4); adiinstEdge(o, 3, 3) ad i ns entedae1, 3, 2); adiinstEdge(2, 3, 5); cout << "Minimum cycle value: "<<adj. computeMinimumCycle () ex); << endl; return 0;

Copyable Code:

Sample Output: I.ll Result Sg++ -o main .cpp $main Minimum cycle value: 6

//header file
#include<bits/stdc++.h>
//for cin and cout
using namespace std;
//define the infinity value
# define INFVALUE 0x3f3f3f3f
//structure for edge data
struct edgeDetail
{
//declare required variable
int sv;
int dv;
int weight;
};
//class for undirected udGraph
class udGraph
{
int vertex;
//declare the adjacent in list
list <pair <int, int>>*A;
//for stores the data of every edge
vector <edgeDetail> ed;
public:
//constructor for udGraph
udGraph(int vertex)
{
this->vertex = vertex;
A = new list <pair<int, int>>[vertex];
}
//function declaration
void insertEdge(int sv, int dv, int w);
void deleteEdge(int sv, int dv, int w);
int computeMinimumPath(int sv, int dv);
void deleteEdge(int sv, int dv);
int computeMinimumCycle();

};
//function definition for insert edge into given graph
void udGraph :: insertEdge(int sv, int dv, int w1)
{
//push back
A[sv].push_back(make_pair(dv, w1));
A[dv].push_back(make_pair(sv, w1));
//insert edge to given edge list
edgeDetail e1 {sv, dv, w1};
ed.push_back (e1);
}
//function definition for delete edge from given graph
void udGraph :: deleteEdge(int sv, int dv, int w1)
{
//for delete edge
A[sv].remove(make_pair(dv, w1));
A[dv].remove(make_pair(sv, w1));
}
//function definition for compute minimum path
//using Dijikstra’s shortest path algorithm
int udGraph::computeMinimumPath(int sv, int dv)
{
set<pair<int, int>> s;
//generate a vector for distances
//initializes the infinity for every distance
vector<int> d(vertex, INFVALUE);
//insert the source itself
s.insert(make_pair(0, sv));
d[sv] = 0;
while (!s.empty())
{
pair<int, int> t = *(s.begin());
s.erase(s.begin());
int sv = t.second;
list< pair<int, int> >::iterator it;
for (it = A[sv].begin(); it != A[sv].end(); ++it)
{
int dv = (*it).first;
int weight = (*it).second;
//If there is minimum path to dv by su, then
if (d[dv] > d[sv] + weight)
{
///check below condition
if (d[dv] != INFVALUE)
s.erase(s.find(make_pair(d[dv], dv)));
//altering the distance of dv
d[dv] = d[sv] + weight;
s.insert(make_pair(d[dv], dv));
}
}
}
//return shortest path
return d[dv] ;
}
//function definition for find minimum weighted cycle
int udGraph :: computeMinimumCycle()
{
//for minimum cycle
int mc = INT_MAX;
//size
int te = ed.size();
for (int r = 0 ; r < te ; r++)
{
//existing Edge data
edgeDetail e = ed[r];
//call deleteEdge() function
deleteEdge(e.sv, e.dv, e.weight);
//compute minimum distance between 2 vertices
int md = computeMinimumPath(e.sv, e.dv);
//compute minimum cycle value
mc = min(mc, md + e.weight );
//call insertEdge()
insertEdge(e.sv, e.dv, e.weight );
}
return mc ;
}
//main function
int main()
{
int totalVertex = 9;
//create object for given undirected graph class udGraph
udGraph adj(totalVertex);
//create graph
adj.insertEdge(0, 1, 1);
adj.insertEdge(0, 2, 4);
adj.insertEdge(0, 3, 3);
adj.insertEdge(1, 3, 2);
adj.insertEdge(2, 3, 5);
cout << "Minimum cycle value: "<<adj.computeMinimumCycle() << endl;
return 0;
}