# Minimum weight cycle in an undirected graph

Here given code implementation process.

``````//C Program
//Minimum weight cycle in an undirected graph
#include <stdio.h>

#include <stdlib.h>

#include <limits.h> //for INT_MAX

struct AjlistNode {
int vId; //Vertices id
int weight;
struct AjlistNode *next;
};

struct Graph {
int data; //node key value
struct AjlistNode *next;
};

int size; //number of nodes

//set node key value
void set_data(struct Graph *node) {
if (node != NULL && size > 0) {
int index = 0;
for (index; index < size; index++) {
//set vertic node data
node[index].data = index; //set node key
//Initial no AjlistNode
//set NULL Value
node[index].next = NULL;
}
} else {
printf("Vertic Node is Empty");
}
}
void connect_edge(struct Graph *node, int V, int E, int weight) {

struct AjlistNode *newEdge = (struct AjlistNode *) malloc(
sizeof(struct AjlistNode)
);
if (newEdge != NULL) {

newEdge->next = NULL;
newEdge->vId = E;
newEdge->weight = weight;

struct AjlistNode *temp = node[V].next;

if (temp == NULL) {
node[V].next = newEdge;
} else {
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newEdge;
}
} else {
printf("\n Memory overflow");

}
}
//Add Edge from Two given Nodes
void add_edge(struct Graph *node, int V, int E, int weight) {
//add edge form V to E
//V and E is Node location
if (V < size && E < size) {

connect_edge(node, V, E, weight);
if (V == E) {
return;
}
connect_edge(node, E, V, weight);
} else {
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V, E);
}
}
void print_graph(struct Graph *node)

{
if (node != NULL)

{
struct AjlistNode *temp = NULL;
for (int index = 0; index < size; index++) {
printf("\n Adjacency list of vertex %d  :", index);
temp = node[index].next;
while (temp != NULL) {
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d", node[temp->vId].data);
temp = temp->next;
}
}
} else {
printf("Empty Graph");
}
}

void minimum_cycle(int start, int end, int *visit,
struct Graph *node, int *result, int length, int sum) {

if (start > size || end > size || start < 0 || end < 0 && node == NULL) {
//invalid input
return;
}

if (visit[start] == 1) {

if (start == end && length > 2 && sum < *result) {

*result = sum;
}

return;
}

visit[start] = 1;

struct AjlistNode *temp = node[start].next;

while (temp != NULL) {
minimum_cycle(temp->vId, end, visit, node, result, length + 1, sum + (temp->weight));

temp = temp->next;
}

visit[start] = 0;
}

void node_cycle_weight(struct Graph *node) {

int visit[size];

int result = INT_MAX;
for (int i = 0; i < size; ++i) {
visit[i] = 0;
}
for (int i = 0; i < size; ++i) {

minimum_cycle(i, i, visit, node, & result, 0, 0);
}
if (result == INT_MAX) {
//Assuming that exist cycle weight less than INT_MAX
printf("\n Min weight cycle : None");
} else {
printf("\n Min weight cycle : %d \n", result);
}
}
int main()

{

size = 6;
struct Graph *node = NULL;

node = (struct Graph *) malloc(sizeof(struct Graph) *size);

if (node == NULL) {
printf("\n Memory overflow");
} else {
//First set node keys
set_data(node);

//Connected two node with Edges

print_graph(node);
node_cycle_weight(node);

}
return 0;
}```
```

#### Output

`````` Adjacency list of vertex 0  :  1  3  4  5
Adjacency list of vertex 1  :  0  2  4  5
Adjacency list of vertex 2  :  1  3  5
Adjacency list of vertex 3  :  0  2  4
Adjacency list of vertex 4  :  0  1  3  5
Adjacency list of vertex 5  :  0  2  4  1
Min weight cycle : 3``````
``````// C++ Program
// Minimum weight cycle in an directed graph
#include<iostream>
#include <limits.h> //for INT_MAX
using namespace std;
class AjlistNode {
public:

//Vertices node key
int id;
int weight;
AjlistNode *next;
AjlistNode(int id, int weight) {
//Set value of node key
this->id = id;
this->weight = weight;
this->next = NULL;
}
};
class Vertices {
public:
int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int data) {
this->data = data;
this->next = NULL;
}
};
class MyGraph {
public:

//Number of Vertices
int size;
Vertices *node;
int result;
MyGraph(int size) {
//set value
this->size = size;
this->result = 0;
this->node = new Vertices[size];
this->set_data();
}
//Set initial node value
void set_data() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
for (int index = 0; index < this->size; index++) {
this->node[index] = index;
}
}
}
//Connect two nodes
void connect(int start, int last, int weight) {
AjlistNode *new_edge = new AjlistNode(last, weight);
if (this->node[start].next == NULL) {
this->node[start].next = new_edge;
} else {
AjlistNode *temp = this->node[start].next;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_edge;
}
}
void add_edge(int start, int last, int weight) {
if (start >= 0 &&
start < this->size &&
last >= 0 &&
last < this->size &&
this->node != NULL) {
this->connect(start, last, weight);
if (start != last) {
this->connect(last, start, weight);
}
} else {
cout << "\nHere Something Wrong";
}
}
void print_graph() {
if (this->size > 0 &&
this->node != NULL) {
for (int index = 0; index < this->size; index++) {
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << " " << this->node[temp->id].data;
temp = temp->next;
}
}
}
}
void minimum_cycle(int start, int last, bool visit[], int cycle_size, int sum) {
if (start > this->size ||
last > this->size ||
start < 0 ||
last < 0 &&
this->node == NULL) {
return;
}
if (visit[start] == true) {
if (start == last &&
sum < this->result &&
cycle_size > 2) {
//When find a new min weight cycle
this->result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;
//This is used to iterate nodes edges
AjlistNode *temp = this->node[start].next;
while (temp != NULL) {
this->minimum_cycle(temp->id, last, visit, cycle_size + 1, sum + (temp->weight));
//visit to next edge
temp = temp->next;
}
// Reset the value of visited node status
visit[start] = false;
}
void min_cycle_weight() {
bool *visit = new bool[size];
//Set initial visited node status

for (int i = 0; i < this->size; ++i) {
visit[i] = false;
}
this->result = INT_MAX;
for (int i = 0; i < this->size; ++i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
this->minimum_cycle(i, i, visit, 0, 0);
}
if (this->result == INT_MAX) {
cout << "\n Min weight cycle : None \n";
} else {
cout << "\n Min weight cycle : " << this->result << "\n";
}
}
};
int main() {
//6 implies the number of nodes in graph
MyGraph g =  MyGraph(6);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g.print_graph();
g.min_cycle_weight();
return 0;
}```
```

#### Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4 5
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 1
Min weight cycle : 3``````
``````// Java Program
// Minimum weight cycle in an directed graph

class AjlistNode {
//Vertices node key
public int id;
public int weight;
public AjlistNode next;

public AjlistNode(int id,int weight) {
//Set value of node key
this.id = id;
this.weight=weight;
this.next = null;
}
}
class Vertices {

public int data;
public AjlistNode next;

public Vertices(int data) {
this.data = data;
this.next = null;
}
}

public class MyGraph
{

//Number of Vertices
public int size;

public Vertices []node;
public int result;
public MyGraph(int size)
{
//set value
this.size = size;
this.result = 0;
this.node = new Vertices[size];
this.set_data();

}

//Set initial node value
public void set_data()
{
if(node == null)
{
System.out.println("\nEmpty Graph");
}else
{
for(int index=0;index<size;index++)
{

node[index]=new Vertices(index);
}
}
}

//Connect two nodes
public void connect(int start,int last ,int weight)
{
AjlistNode new_edge=new AjlistNode(last,weight);

if(node[start].next==null)
{
node[start].next=new_edge;
}else
{
AjlistNode temp=node[start].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=new_edge;
}
}
public void add_edge(int start,int last,int weight)
{
if(start>=0 && start < size && last >= 0 &&  last < size && node != null)
{
connect(start,last,weight);
if(start!=last)
{
connect(last,start,weight);
}

}else
{
System.out.println("\nHere Something Wrong");
}
}

public void print_graph()
{

if(size >0 && node!=null)
{
for(int index = 0; index < size; index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");
AjlistNode temp = node[index].next;
while(temp != null)
{
System.out.print("  "+node[temp.id].data);
temp=temp.next;
}
}
}
}

public void minimum_cycle(int start, int last, boolean[] visit,int cycle_size,int sum)
{
if (start > size || last > size || start < 0
|| last < 0 && node == null) {
return;
}
if (visit[start] == true) {

if (start == last && sum < result && cycle_size >2)
{

//When find a new min weight cycle
result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;

//This is used to iterate nodes edges
AjlistNode temp = node[start].next;

while (temp != null)
{
minimum_cycle(temp.id, last, visit,cycle_size+1, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[start] = false;
}

public void min_cycle_weight() {
//Auxiliary space which is used to store information about visited node
boolean[] visit = new boolean[size];

//Set initial visited node status
for (int i = 0; i < size; ++i)
{
visit[i] = false;
}
this.result = Integer.MAX_VALUE;

for (int i = 0; i < size; ++i)
{
//Check cycle of node i to i
//Here initial cycle weight is zero
minimum_cycle(i, i, visit, 0,0);

}
if (result == Integer.MAX_VALUE)
{
System.out.print("\n Min weight cycle : None \n");
} else {
System.out.print("\n Min weight cycle : "+this.result+"\n");
}
}
public static void main(String[] args)
{

//6 implies the number of nodes in graph
MyGraph g=new MyGraph(6);

//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge

g.print_graph();
g.min_cycle_weight();
}
}```
```

#### Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4 5
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 1
Min weight cycle : 3``````
``````// C# Program
// Minimum weight cycle in an directed graph
using System;
public class AjlistNode {
//Vertices node key
public int id;
public int weight;
public AjlistNode next;
public AjlistNode(int id, int weight) {
//Set value of node key
this.id = id;
this.weight = weight;
this.next = null;
}
}
public class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//Number of Vertices
public int size;
public Vertices[] node;
public int result;
public MyGraph(int size) {
//set value
this.size = size;
this.result = 0;
this.node = new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {
for (int index = 0; index < size; index++) {
node[index] = new Vertices(index);
}
}
}
//Connect two nodes
public void connect(int start, int last, int weight) {
AjlistNode new_edge = new AjlistNode(last, weight);
if (node[start].next == null) {
node[start].next = new_edge;
} else {
AjlistNode temp = node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
public void add_edge(int start, int last, int weight) {
if (start >= 0 &&
start < size &&
last >= 0 &&
last < size &&
node != null) {
connect(start, last, weight);
if (start != last) {
connect(last, start, weight);
}
} else {
Console.WriteLine("\nHere Something Wrong");
}
}
public void print_graph() {
if (size > 0 &&
node != null) {
for (int index = 0; index < size; index++) {
Console.Write("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(" " + node[temp.id].data);
temp = temp.next;
}
}
}
}
public void minimum_cycle(int start, int last, Boolean[] visit, int cycle_size, int sum) {
if (start > size ||
last > size ||
start < 0 ||
last < 0 &&
node == null) {
return;
}
if (visit[start] == true) {
if (start == last &&
sum < result &&
cycle_size > 2) {
//When find a new min weight cycle
result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;
//This is used to iterate nodes edges
AjlistNode temp = node[start].next;
while (temp != null) {
minimum_cycle(temp.id, last, visit, cycle_size + 1, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[start] = false;
}
public void min_cycle_weight() {
Boolean[]
//Auxiliary space which is used to store information about visited node
visit = new Boolean[size];
//Set initial visited node status

for (int i = 0; i < size; ++i) {
visit[i] = false;
}
this.result = int.MaxValue;
for (int i = 0; i < size; ++i) {
minimum_cycle(i, i, visit, 0, 0);
}
if (result == int.MaxValue) {
Console.Write("\n Min weight cycle : None \n");
} else {
Console.Write("\n Min weight cycle : " + this.result + "\n");
}
}
public static void Main(String[] args) {
//6 implies the number of nodes in graph
MyGraph g = new MyGraph(6);
g.print_graph();
g.min_cycle_weight();
}
}```
```

#### Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4 5
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 1
Min weight cycle : 3``````
``````<?php
// Php Program
// Minimum weight cycle in an directed graph
class AjlistNode {
//Vertices node key
public \$id;
public \$weight;
public \$next;

function __construct(\$id, \$weight) {
//Set value of node key
\$this->id = \$id;
\$this->weight = \$weight;
\$this->next = null;
}
}
class Vertices {
public \$data;
public \$next;

function __construct(\$data) {
\$this->data = \$data;
\$this->next = null;
}
}
class MyGraph {
//Number of Vertices
public \$size;
public \$node;
public \$result;

function __construct(\$size) {
//set value
\$this->size = \$size;
\$this->result = 0;
\$this->node = array_fill(0, \$size, null);
\$this->set_data();
}
//Set initial node value
public 	function set_data() {
if (\$this->node == null) {
echo("\nEmpty Graph");
} else {
for (\$index = 0; \$index < \$this->size; \$index++) {
\$this->node[\$index] = new Vertices(\$index);
}
}
}
//Connect two nodes
public 	function connect(\$start, \$last, \$weight) {
\$new_edge = new AjlistNode(\$last, \$weight);
if (\$this->node[\$start]->next == null) {
\$this->node[\$start]->next = \$new_edge;
} else {
\$temp = \$this->node[\$start]->next;
while (\$temp->next != null) {
\$temp = \$temp->next;
}
\$temp->next = \$new_edge;
}
}
public 	function add_edge(\$start, \$last, \$weight) {
if (\$start >= 0 &&
\$start < \$this->size &&
\$last >= 0 &&
\$last < \$this->size &&
\$this->node != null) {
\$this->connect(\$start, \$last, \$weight);
if (\$start != \$last) {
\$this->connect(\$last, \$start, \$weight);
}
} else {
echo("\nHere Something Wrong");
}
}
public 	function print_graph() {
if (\$this->size > 0 &&
\$this->node != null) {
for (\$index = 0; \$index < \$this->size; \$index++) {
echo("\nAdjacency list of vertex ". \$index ." :");
\$temp = \$this->node[\$index]->next;
while (\$temp != null) {
echo(" ". \$this->node[\$temp->id]->data);
\$temp = \$temp->next;
}
}
}
}
public 	function minimum_cycle(\$start, \$last, & \$visit, \$cycle_size, \$sum) {
if (\$start > \$this->size ||
\$last > \$this->size ||
\$start < 0 ||
\$last < 0 &&
\$this->node == null) {
return;
}
if (\$visit[\$start] == true) {
if (\$start == \$last &&
\$sum < \$this->result &&
\$cycle_size > 2) {
//When find a new min weight cycle
\$this->result = \$sum;
}
return;
}
//Here modified  the value of visited node
\$visit[\$start] = true;
//This is used to iterate nodes edges
\$temp = \$this->node[\$start]->next;
while (\$temp != null) {
\$this->minimum_cycle(\$temp->id, \$last, \$visit, \$cycle_size + 1, \$sum + (\$temp->weight));
//visit to next edge
\$temp = \$temp->next;
}
// Reset the value of visited node status
\$visit[\$start] = false;
}
public 	function min_cycle_weight() {
//Auxiliary space which is used to store information about visited node
\$visit = array_fill(0, \$this->size, false);
//Set initial visited node status

for (\$i = 0; \$i < \$this->size; ++\$i) {
\$visit[\$i] = false;
}
\$this->result = PHP_INT_MAX;
for (\$i = 0; \$i < \$this->size; ++\$i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
\$this->minimum_cycle(\$i, \$i, \$visit, 0, 0);
}
if (\$this->result == PHP_INT_MAX) {
echo("\n Min weight cycle : None \n");
} else {
echo("\n Min weight cycle : ". \$this->result ."\n");
}
}
}

function main() {
//6 implies the number of nodes in graph
\$g = new MyGraph(6);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
\$g->print_graph();
\$g->min_cycle_weight();

}
main();```
```

#### Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4 5
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 1
Min weight cycle : 3``````
``````// Node Js Program
// Minimum weight cycle in an directed graph
class AjlistNode {
//Vertices node key

constructor(id, weight) {
//Set value of node key
this.id = id;
this.weight = weight;
this.next = null;
}
}
class Vertices {
constructor(data) {
this.data = data;
this.next = null;
}
}
class MyGraph {
//Number of Vertices

constructor(size) {
//set value
this.size = size;
this.result = 0;
this.node = Array(size).fill(null);
this.set_data();
}

//Set initial node value
set_data() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
for (var index = 0; index < this.size; index++) {
this.node[index] = new Vertices(index);
}
}
}

//Connect two nodes
connect(start, last, weight) {
var new_edge = new AjlistNode(last, weight);
if (this.node[start].next == null) {
this.node[start].next = new_edge;
} else {
var temp = this.node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}

if (start >= 0 &&
start < this.size &&
last >= 0 &&
last < this.size &&
this.node != null) {
this.connect(start, last, weight);
if (start != last) {
this.connect(last, start, weight);
}
} else {
process.stdout.write("\nHere Something Wrong");
}
}
print_graph() {
if (this.size > 0 &&
this.node != null) {
for (var index = 0; index < this.size; index++) {
process.stdout.write("\nAdjacency list of vertex " + index + " :");
var temp = this.node[index].next;
while (temp != null) {
process.stdout.write(" " + this.node[temp.id].data);
temp = temp.next;
}
}
}
}
minimum_cycle(start, last, visit, cycle_size, sum) {
if (start > this.size ||
last > this.size ||
start < 0 ||
last < 0 &&
this.node == null) {
return;
}

if (visit[start] == true) {
if (start == last &&
sum < this.result &&
cycle_size > 2) {
//When find a new min weight cycle
this.result = sum;
}

return;
}

//Here modified  the value of visited node
visit[start] = true;
//This is used to iterate nodes edges
var temp = this.node[start].next;
while (temp != null) {
this.minimum_cycle(temp.id, last, visit, cycle_size + 1, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}

// Reset the value of visited node status
visit[start] = false;
}
min_cycle_weight() {
//Auxiliary space which is used to store information about visited node
var visit = Array(this.size).fill(false);
//Set initial visited node status

for (var i = 0; i < this.size; ++i) {
visit[i] = false;
}
this.result = Number.MAX_VALUE;
for (var i = 0; i < this.size; ++i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
this.minimum_cycle(i, i, visit, 0, 0);
}

if (this.result == Number.MAX_VALUE) {
process.stdout.write("\n Min weight cycle : None \n");
} else {
process.stdout.write("\n Min weight cycle : " + this.result + "\n");
}
}
}

function main(args) {
//6 implies the number of nodes in graph
var g = new MyGraph(6);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g.print_graph();
g.min_cycle_weight();
}

main();```
```

#### Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4 5
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 1
Min weight cycle : 3``````
``````#  Python 3 Program
#  Minimum weight cycle in an directed graph
import sys
class AjlistNode :
# Vertices node key
def __init__(self, id, weight) :
# Set value of node key
self.id = id
self.weight = weight
self.next = None

class Vertices :

def __init__(self, data) :
self.data = data
self.next = None

class MyGraph :
# Number of Vertices
def __init__(self, size) :
# set value
self.size = size
self.result = 0
self.node = [None] * size
self.set_data()

# Set initial node value
def set_data(self) :
if (self.node == None) :
print("\nEmpty Graph", end = "")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1

# Connect two nodes
def connect(self, start, last, weight) :
new_edge = AjlistNode(last, weight)
if (self.node[start].next == None) :
self.node[start].next = new_edge
else :
temp = self.node[start].next
while (temp.next != None) :
temp = temp.next

temp.next = new_edge

# Add edge of two nodes
def add_edge(self, start, last, weight) :
if (start >= 0 and start < self.size and
last >= 0 and last < self.size and self.node != None) :
self.connect(start, last, weight)
if (start != last) :
self.connect(last, start, weight)

else :
print("\nHere Something Wrong", end = "")

def print_graph(self) :
if (self.size > 0 and self.node != None) :
index = 0
while (index < self.size) :
print("\nAdjacency list of vertex ", index ," :", end = "")
temp = self.node[index].next
while (temp != None) :
print(" ", self.node[temp.id].data, end = "")
temp = temp.next

index += 1

def minimum_cycle(self, start, last, visit, cycle_size, sum) :
if (start > self.size or last > self.size
or start < 0 or last < 0 and self.node == None) :
return

if (visit[start] == True) :
if (start == last and sum < self.result and cycle_size > 2) :
# When find a new min weight cycle
self.result = sum

return

# Here modified  the value of visited node
visit[start] = True
temp = self.node[start].next
while (temp != None) :
self.minimum_cycle(temp.id, last, visit, cycle_size + 1, sum + (temp.weight))
# visit to next edge
temp = temp.next

#  Reset the value of visited node status
visit[start] = False

def min_cycle_weight(self) :
visit = [False] * self.size
# Set initial visited node status
i = 0
while (i < self.size) :
visit[i] = False
i += 1

self.result = sys.maxsize
i = 0
while (i < self.size) :
self.minimum_cycle(i, i, visit, 0, 0)
i += 1

if (self.result == sys.maxsize) :
print("\n Min weight cycle : None \n", end = "")
else :
print("\n Min weight cycle : ", self.result ,"\n", end = "")

def main() :
# 6 implies the number of nodes in graph
g = MyGraph(6)
# Connected two node with Edges
# First two parameter indicates number start and last nodes
# And third parameter indicates weight of edge
g.print_graph()
g.min_cycle_weight()

if __name__ == "__main__":
main()```
```

#### Output

``````Adjacency list of vertex  0  :  1  3  4  5
Adjacency list of vertex  1  :  0  2  4  5
Adjacency list of vertex  2  :  1  3  5
Adjacency list of vertex  3  :  0  2  4
Adjacency list of vertex  4  :  0  1  3  5
Adjacency list of vertex  5  :  0  2  4  1
Min weight cycle :  3``````
``````#  Ruby Program
#  Minimum weight cycle in an directed graph
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_accessor :id, :weight, :next
# Vertices node key
def initialize(id, weight)
# Set value of node key
self.id = id
self.weight = weight
self.next = nil
end
end
class Vertices
# Define the accessor and reader of class Vertices
attr_accessor :data, :next

def initialize(data)
self.data = data
self.next = nil
end
end
class MyGraph
# Define the accessor and reader of class MyGraph
attr_accessor :size, :node, :result
# Number of Vertices
def initialize(size)
# set value
self.size = size
self.result = 0
self.node = Array.new(size) {nil}
self.set_data()
end
# Set initial node value
def set_data()
if (@node == nil)
print("\nEmpty Graph")
else
index = 0
while (index < @size)
@node[index] = Vertices.new(index)
index += 1
end
end
end
# Connect two nodes
def connect(start, last, weight)
new_edge = AjlistNode.new(last, weight)
if (@node[start].next == nil)
@node[start].next = new_edge
else
temp = @node[start].next
while (temp.next != nil)
temp = temp.next
end
temp.next = new_edge
end
end
# Add edge of two nodes
if (start >= 0 &&
start < @size &&
last >= 0 &&
last < @size &&
@node != nil)
self.connect(start, last, weight)
if (start != last)
self.connect(last, start, weight)
end
else
print("\nHere Something Wrong")
end
end
def print_graph()
if (@size > 0 &&
@node != nil)
index = 0
while (index < @size)
print("\nAdjacency list of vertex ", index ,"  :")
temp = @node[index].next
while (temp != nil)
print(" ", @node[temp.id].data)
temp = temp.next
end
index += 1
end
end
end
def minimum_cycle(start, last, visit, cycle_size, sum)
if (start > @size ||
last > @size ||
start < 0 ||
last < 0 &&
@node == nil)
return
end
if (visit[start] == true)
if (start == last &&
sum < @result &&
cycle_size > 2)
# When find a new min weight cycle
@result = sum
end
return
end
# Here modified  the value of visited node
visit[start] = true
temp = @node[start].next
while (temp != nil)
self.minimum_cycle(temp.id, last, visit, cycle_size + 1, sum + (temp.weight))
# visit to next edge
temp = temp.next
end
#  Reset the value of visited node status
visit[start] = false
end
def min_cycle_weight()
visit = Array.new(@size) {false}
# Set initial visited node status
i = 0
while (i < @size)
visit[i] = false
i += 1
end
self.result = (2 ** (0. size * 8 - 2))
i = 0
while (i < @size)
self.minimum_cycle(i, i, visit, 0, 0)
i += 1
end
if (@result == (2 ** (0. size * 8 - 2)))
print("\n Min weight cycle  :None \n")
else
print("\n Min weight cycle  :", self.result ,"\n")
end
end
end
def main()
# 6 implies the number of nodes in graph
g = MyGraph.new(6)
# Connected two node with Edges
# First two parameter indicates number start and last nodes
# And third parameter indicates weight of edge
g.print_graph()
g.min_cycle_weight()
end
main()```
```

#### Output

``````Adjacency list of vertex 0  : 1 3 4 5
Adjacency list of vertex 1  : 0 2 4 5
Adjacency list of vertex 2  : 1 3 5
Adjacency list of vertex 3  : 0 2 4
Adjacency list of vertex 4  : 0 1 3 5
Adjacency list of vertex 5  : 0 2 4 1
Min weight cycle  :3
``````
``````// Scala Program
// Minimum weight cycle in an directed graph
class AjlistNode(var id: Int,
var next: AjlistNode,
var weight: Int) {

def this(id: Int, weight: Int) {
//Set value
this(id,null,weight);
}
}
class Vertices(var data: Int,
var next: AjlistNode) {

def this(data: Int) {
this(data,null);
}
}
class MyGraph(var size: Int,
var node: Array[Vertices],
var result: Int) {
//Number of Vertices
def this(size: Int) {
this(size,Array.fill[Vertices](size)(null),0);
this.set_data();
}
//Set initial node value
def set_data(): Unit = {
if (node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < size) {
node(index) = new Vertices(index);
index += 1;
}
}
}
//Connect two nodes
def connect(start: Int, last: Int, weight: Int): Unit = {
var new_edge: AjlistNode = new AjlistNode(last, weight);

if (node(start).next == null) {
node(start).next = new_edge;
} else {
var temp: AjlistNode = node(start).next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
def add_edge(start: Int, last: Int, weight: Int): Unit = {
if (start >= 0 &&
start < size &&
last >= 0 &&
last < size &&
node != null) {
connect(start, last, weight);

if (start != last) {
connect(last, start, weight);
}
} else {
print("\nHere Something Wrong");
}
}
def print_graph(): Unit = {
if (size > 0 &&
node != null) {
var index: Int = 0;
while (index < size) {
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = node(index).next;
while (temp != null) {
print(" " + node(temp.id).data);
temp = temp.next;
}
index += 1;
}
}
}
def minimum_cycle(start: Int, last: Int, visit: Array[Boolean], cycle_size: Int, sum: Int): Unit = {
if (start > size ||
last > size ||
start < 0 ||
last < 0 &&
node == null) {
return;
}
if (visit(start) == true) {
if (start == last &&
sum < result &&
cycle_size > 2) {
//When find a new min weight cycle
result = sum;
}
return;
}
//Here modified  the value of visited node
visit(start) = true;
var temp: AjlistNode = node(start).next;
while (temp != null) {
minimum_cycle(temp.id, last, visit, cycle_size + 1, sum + (temp.weight));

//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit(start) = false;
}
def min_cycle_weight(): Unit = {
var visit:Array[Boolean] = Array.fill[Boolean](this.size)(false);

//Set initial visited node status
var i: Int = 0;
while (i < size) {
visit(i) = false;
i += 1;
}
this.result = Int.MaxValue;
i = 0;
while (i < size) {
minimum_cycle(i, i, visit, 0, 0);
i += 1;
}
if (result == Int.MaxValue) {
print("\n Min weight cycle : None \n");
} else {
print("\n Min weight cycle : " + this.result + "\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
//6 implies the number of nodes in graph
var g: MyGraph = new MyGraph(6);

//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g.print_graph();
g.min_cycle_weight();
}
}```
```

#### Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4 5
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 1
Min weight cycle : 3``````
``````// Swift Program
// Minimum weight cycle in an directed graph
class AjlistNode {
//Vertices node key
var id: Int;
var weight: Int;
var next: AjlistNode? ;
init(_ id: Int, _ weight: Int) {
//Set value of node key
self.id = id;
self.weight = weight;
self.next = nil;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ value: Int) {
self.data = value;
self.next = nil;
}
}
class MyGraph {
//Number of Vertices
var size: Int;
var node: [Vertices]? = [Vertices]() ;
var result: Int;
init(_ size: Int) {
//set value
self.size = size;
self.result = 0;
var i = 0;
while (i<size) {
self.node!.append(Vertices(i));
i+=1;
}
}
//Connect two nodes
func connect(_ start: Int, _ last: Int, _ weight: Int) {
let new_edge: AjlistNode? = AjlistNode(last, weight);
if (self.node![start].next == nil) {
self.node![start].next = new_edge;
} else {
var temp: AjlistNode? = self.node![start].next;
while (temp!.next != nil) {
temp = temp!.next;
}
temp!.next = new_edge;
}
}
func add_edge(_ start: Int, _ last: Int, _ weight: Int) {
if (start >= 0 &&
start < self.size &&
last >= 0 &&
last < self.size &&
self.node != nil) {
self.connect(start, last, weight);
if (start != last) {
self.connect(last, start, weight);
}
} else {
print("\nHere Something Wrong", terminator: "");
}
}
func print_graph() {
if (self.size > 0 &&
self.node != nil) {
var index: Int = 0;
while (index < self.size) {
print("\nAdjacency list of vertex ", index ," :", terminator: "");
var temp: AjlistNode? = self.node![index].next;
while (temp != nil) {
print(" ", self.node![temp!.id].data, terminator: "");
temp = temp!.next;
}
index += 1;
}
}
}
func minimum_cycle(_ start: Int, _ last: Int, _ visit: inout[Bool], _ cycle_size: Int, _ sum: Int) {
if (start > self.size ||
last > self.size ||
start < 0 ||
last < 0 &&
self.node == nil) {
return;
}
if (visit[start] == true) {
if (start == last &&
sum < self.result &&
cycle_size > 2) {
//When find a new min weight cycle
self.result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;
var temp: AjlistNode? = self.node![start].next;
while (temp != nil) {
self.minimum_cycle(temp!.id, last, &visit, cycle_size + 1, sum + (temp!.weight));
//visit to next edge
temp = temp!.next;
}
// Reset the value of visited node status
visit[start] = false;
}
func min_cycle_weight() {
var visit: [Bool] = Array(repeating: false, count: self.size);
//Set initial visited node status
var i: Int = 0;
while (i < self.size) {
visit[i] = false;
i += 1;
}
self.result = Int.max;
i = 0;
while (i < self.size) {
self.minimum_cycle(i, i, &visit, 0, 0);
i += 1;
}
if (self.result == Int.max) {
print("\n Min weight cycle : None \n", terminator: "");
} else {
print("\n Min weight cycle : ", self.result ,"\n", terminator: "");
}
}
}
func main() {
//6 implies the number of nodes in graph
let g: MyGraph? = MyGraph(6);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g!.print_graph();
g!.min_cycle_weight();
}
main();```
```

#### Output

``````Adjacency list of vertex  0  :  1  3  4  5
Adjacency list of vertex  1  :  0  2  4  5
Adjacency list of vertex  2  :  1  3  5
Adjacency list of vertex  3  :  0  2  4
Adjacency list of vertex  4  :  0  1  3  5
Adjacency list of vertex  5  :  0  2  4  1
Min weight cycle :  3``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.