Travelling salesman problem using backtracking

Here given code implementation process.

/*
    Java Program for
    Travelling salesman problem using backtracking
*/
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 Graph
{
	// Number of Vertices
	public int size;
	public Vertices[] node;
	public int result;
	public Graph(int size)
	{
		// Set value
		this.size = size;
		this.node = new Vertices[size];
		this.result = Integer.MAX_VALUE;
		this.setData();
	}
	// Set initial node value
	public void setData()
	{
		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;
		}
	}
	// Add edge of two nodes
	public void addEdge(int start, int last, int weight)
	{
		if (start >= 0 && start < size && last >= 0 && 
            last < size && node != null)
		{
			connect(start, last, weight);
			if (start == last)
			{
				// Self looping situation
				return;
			}
			connect(last, start, weight);
		}
		else
		{
			System.out.println("\nHere Something Wrong");
		}
	}
	public void printGraph()
	{
		if (size > 0 && node != null)
		{
			// Print graph ajlist Node value
			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);
					// visit to next edge
					temp = temp.next;
				}
			}
		}
	}
	public void findMinPath(int source, 
      int index, 
      boolean[] visit, 
      int sum, 
      int count)
	{
		if (source == index && count == this.size)
		{
			// When reached all other vertex and back to source vertex
			if (this.result > sum)
			{
				this.result = sum;
			}
			return;
		}
		if (visit[index] == true)
		{
			return;
		}
		// Here modified  the value of visited node
		visit[index] = true;
		// This is used to iterate nodes edges
		AjlistNode temp = node[index].next;
		while (temp != null)
		{
			findMinPath(source, temp.id, visit, 
                        sum + (temp.weight), count + 1);
			// Visit to next edge
			temp = temp.next;
		}
		// Reset the value of visited node status
		visit[index] = false;
	}
	public void travllingSalesmanProblem(int source)
	{
		this.result = Integer.MAX_VALUE;
		boolean[] visit = new boolean[this.size];
		// Set initial visited node status 
		for (int i = 0; i < size; ++i)
		{
			visit[i] = false;
		}
		System.out.print("\n Source node : " + source);
		findMinPath(source, source, visit, 0, 0);
		System.out.print("\n Result : " + this.result);
	}
	public static void main(String[] args)
	{
		// 5 implies the number of nodes in graph
		Graph g = new Graph(5);
		g.addEdge(0, 1, 7);
		g.addEdge(0, 2, 4);
		g.addEdge(0, 3, 8);
		g.addEdge(0, 4, 6);
		g.addEdge(1, 2, 5);
		g.addEdge(1, 3, 5);
		g.addEdge(1, 4, 1);
		g.addEdge(2, 3, 5);
		g.addEdge(2, 4, 4);
		g.addEdge(3, 4, 3);
		// print graph element
		g.printGraph();
		// Test 
		int source = 0;
		g.travllingSalesmanProblem(source);
	}
}

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
/*
    C++ Program for
    Travelling salesman problem using backtracking
*/
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 Graph
{
    public:
    // Number of Vertices
    int size;
    Vertices *node;
    int result;
    Graph(int size)
    {
        // Set value
        this->size = size;
        this->result = INT_MAX;
        this->node = new Vertices[size];
        this->setData();
    }
    // Set initial node value
    void setData()
    {
        if (this->node == NULL)
        {
            cout << "\nEmpty Graph" << endl;
        }
        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;
        }
    }
    // Add edge of two nodes
    void addEdge(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)
            {
                // Self looping situation
                return;
            }
            this->connect(last, start, weight);
        }
        else
        {
            cout << "\nHere Something Wrong" << endl;
        }
    }
    void printGraph()
    {
        if (this->size > 0 && this->node != NULL)
        {
            // Print graph ajlist Node value
            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;
                    // visit to next edge
                    temp = temp->next;
                }
            }
        }
    }
    void findMinPath(int source, int index, 
                     bool visit[], int sum, int count)
    {
        if (source == index && count == this->size)
        {
            // When reached all other vertex and back to source vertex
            if (this->result > sum)
            {
                this->result = sum;
            }
            return;
        }
        if (visit[index] == true)
        {
            return;
        }
        // Here modified  the value of visited node
        visit[index] = true;
        // This is used to iterate nodes edges
        AjlistNode *temp = this->node[index].next;
        while (temp != NULL)
        {
            this->findMinPath(source, temp->id, 
                              visit, sum + (temp->weight), count + 1);
            // Visit to next edge
            temp = temp->next;
        }
        // Reset the value of visited node status
        visit[index] = false;
    }
    void travllingSalesmanProblem(int source)
    {
        this->result = INT_MAX;
        bool visit[this->size];
        // Set initial visited node status 
        for (int i = 0; i < this->size; ++i)
        {
            visit[i] = false;
        }
        cout << "\n Source node : " << source;
        this->findMinPath(source, source, visit, 0, 0);
        cout << "\n Result : " << this->result;
    }
};
int main()
{
    // 5 implies the number of nodes in graph
    Graph *g = new Graph(5);
    g->addEdge(0, 1, 7);
    g->addEdge(0, 2, 4);
    g->addEdge(0, 3, 8);
    g->addEdge(0, 4, 6);
    g->addEdge(1, 2, 5);
    g->addEdge(1, 3, 5);
    g->addEdge(1, 4, 1);
    g->addEdge(2, 3, 5);
    g->addEdge(2, 4, 4);
    g->addEdge(3, 4, 3);
    // print graph element
    g->printGraph();
    // Test 
    int source = 0;
    g->travllingSalesmanProblem(source);
    return 0;
}

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
// Include namespace system
using System;
/*
    Csharp Program for
    Travelling salesman problem using backtracking
*/
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 Graph
{
	// Number of Vertices
	public int size;
	public Vertices[] node;
	public int result;
	public Graph(int size)
	{
		// Set value
		this.size = size;
		this.node = new Vertices[size];
		this.result = int.MaxValue;
		this.setData();
	}
	// Set initial node value
	public void setData()
	{
		if (this.node == null)
		{
			Console.WriteLine("\nEmpty Graph");
		}
		else
		{
			for (int index = 0; index < this.size; index++)
			{
				this.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 (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;
		}
	}
	// Add edge of two nodes
	public void addEdge(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)
			{
				// Self looping situation
				return;
			}
			this.connect(last, start, weight);
		}
		else
		{
			Console.WriteLine("\nHere Something Wrong");
		}
	}
	public void printGraph()
	{
		if (this.size > 0 && this.node != null)
		{
			// Print graph ajlist Node value
			for (int index = 0; index < this.size; ++index)
			{
				Console.Write("\nAdjacency list of vertex " + index + " :");
				AjlistNode temp = this.node[index].next;
				while (temp != null)
				{
					Console.Write("  " + this.node[temp.id].data);
					// visit to next edge
					temp = temp.next;
				}
			}
		}
	}
	public void findMinPath(int source, int index, 
                            Boolean[] visit, int sum, int count)
	{
		if (source == index && count == this.size)
		{
			// When reached all other vertex and back to source vertex
			if (this.result > sum)
			{
				this.result = sum;
			}
			return;
		}
		if (visit[index] == true)
		{
			return;
		}
		// Here modified  the value of visited node
		visit[index] = true;
		// This is used to iterate nodes edges
		AjlistNode temp = this.node[index].next;
		while (temp != null)
		{
			this.findMinPath(source, temp.id, 
                             visit, sum + (temp.weight), count + 1);
			// Visit to next edge
			temp = temp.next;
		}
		// Reset the value of visited node status
		visit[index] = false;
	}
	public void travllingSalesmanProblem(int source)
	{
		this.result = int.MaxValue;
		Boolean[] visit = new Boolean[this.size];
		// Set initial visited node status 
		for (int i = 0; i < this.size; ++i)
		{
			visit[i] = false;
		}
		Console.Write("\n Source node : " + source);
		this.findMinPath(source, source, visit, 0, 0);
		Console.Write("\n Result : " + this.result);
	}
	public static void Main(String[] args)
	{
		// 5 implies the number of nodes in graph
		Graph g = new Graph(5);
		g.addEdge(0, 1, 7);
		g.addEdge(0, 2, 4);
		g.addEdge(0, 3, 8);
		g.addEdge(0, 4, 6);
		g.addEdge(1, 2, 5);
		g.addEdge(1, 3, 5);
		g.addEdge(1, 4, 1);
		g.addEdge(2, 3, 5);
		g.addEdge(2, 4, 4);
		g.addEdge(3, 4, 3);
		// print graph element
		g.printGraph();
		// Test 
		int source = 0;
		g.travllingSalesmanProblem(source);
	}
}

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
package main
import "math"
import "fmt"
/*
    Go Program for
    Travelling salesman problem using backtracking
*/
type AjlistNode struct {
	// Vertices node key
	id int
	weight int
	next * AjlistNode
}
func getAjlistNode(id int, weight int) * AjlistNode {
	var me *AjlistNode = &AjlistNode {}
	// Set value of node key
	me.id = id
	me.weight = weight
	me.next = nil
	return me
}
type Vertices struct {
	data int
	next * AjlistNode
}
func getVertices(data int) * Vertices {
	var me *Vertices = &Vertices {}
	me.data = data
	me.next = nil
	return me
}
type Graph struct {
	// Number of Vertices
	size int
	node [] *Vertices
	result int
}
func getGraph(size int) * Graph {
	var me *Graph = &Graph {}
	// Set value
	me.size = size
	me.node = make([] *Vertices, size)
	me.result = math.MaxInt64
	me.setData()
	return me
}
// Set initial node value
func(this Graph) setData() {
	if this.node == nil {
		fmt.Println("\nEmpty Graph")
	} else {
		for index := 0 ; index < this.size ; index++ {
			this.node[index] = getVertices(index)
		}
	}
}
// Connect two nodes
func(this Graph) connect(start, last, weight int) {
	var new_edge * AjlistNode = getAjlistNode(last, weight)
	if this.node[start].next == nil {
		this.node[start].next = new_edge
	} else {
		var temp * AjlistNode = this.node[start].next
		for (temp.next != nil) {
			temp = temp.next
		}
		temp.next = new_edge
	}
}
// Add edge of two nodes
func(this Graph) addEdge(start, last, weight int) {
	if  start >= 0 && start < this.size && 
		last >= 0 && last < this.size && this.node != nil {
		this.connect(start, last, weight)
		if start == last {
			// Self looping situation
			return
		}
		this.connect(last, start, weight)
	} else {
		fmt.Println("\nHere Something Wrong")
	}
}
func(this Graph) printGraph() {
	if this.size > 0 && this.node != nil {
		// Print graph ajlist Node value
		for index := 0 ; index < this.size ; index++ {
			fmt.Print("\nAdjacency list of vertex ", index, " :")
			var temp * AjlistNode = this.node[index].next
			for (temp != nil) {
				fmt.Print("  ", this.node[temp.id].data)
				// visit to next edge
				temp = temp.next
			}
		}
	}
}
func(this *Graph) findMinPath(source int, index int, visit[] bool, sum int, count int) {
	if source == index && count == this.size {
		// When reached all other vertex and back to source vertex
		if this.result > sum {
			this.result = sum
		}
		return
	}
	if visit[index] == true {
		return
	}
	// Here modified  the value of visited node
	visit[index] = true
	// This is used to iterate nodes edges
	var temp * AjlistNode = this.node[index].next
	for (temp != nil) {
		this.findMinPath(source, temp.id, visit, sum + (temp.weight), count + 1)
		// Visit to next edge
		temp = temp.next
	}
	// Reset the value of visited node status
	visit[index] = false
}
func(this *Graph) travllingSalesmanProblem(source int) {
	this.result = math.MaxInt64
	var visit = make([] bool, this.size)
	// Set initial visited node status 
	for i := 0 ; i < this.size ; i++ {
		visit[i] = false
	}
	fmt.Print("\n Source node : ", source)
	this.findMinPath(source, source, visit, 0, 0)
	fmt.Print("\n Result : ", this.result)
}
func main() {
	// 5 implies the number of nodes in graph
	var g * Graph = getGraph(5)
	g.addEdge(0, 1, 7)
	g.addEdge(0, 2, 4)
	g.addEdge(0, 3, 8)
	g.addEdge(0, 4, 6)
	g.addEdge(1, 2, 5)
	g.addEdge(1, 3, 5)
	g.addEdge(1, 4, 1)
	g.addEdge(2, 3, 5)
	g.addEdge(2, 4, 4)
	g.addEdge(3, 4, 3)
	// print graph element
	g.printGraph()
	// Test 
	var source int = 0
	g.travllingSalesmanProblem(source)
}

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
<?php
/*
    Php Program for
    Travelling salesman problem using backtracking
*/
class AjlistNode
{
	// Vertices node key
	public $id;
	public $weight;
	public $next;
	public	function __construct($id, $weight)
	{
		// Set value of node key
		$this->id = $id;
		$this->weight = $weight;
		$this->next = NULL;
	}
}
class Vertices
{
	public $data;
	public $next;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class Graph
{
	// Number of Vertices
	public $size;
	public $node;
	public $result;
	public	function __construct($size)
	{
		// Set value
		$this->size = $size;
		$this->node = array_fill(0, $size, NULL);
		$this->result = PHP_INT_MAX;
		$this->setData();
	}
	// Set initial node value
	public	function setData()
	{
		if ($this->node == NULL)
		{
			echo("\nEmpty Graph\n");
		}
		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;
		}
	}
	// Add edge of two nodes
	public	function addEdge($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)
			{
				// Self looping situation
				return;
			}
			$this->connect($last, $start, $weight);
		}
		else
		{
			echo("\nHere Something Wrong".
				"\n");
		}
	}
	public	function printGraph()
	{
		if ($this->size > 0 && $this->node != NULL)
		{
			// Print graph ajlist Node value
			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);
					// visit to next edge
					$temp = $temp->next;
				}
			}
		}
	}
	public	function findMinPath($source, $index, $visit, $sum, $count)
	{
		if ($source == $index && $count == $this->size)
		{
			// When reached all other vertex and back to source vertex
			if ($this->result > $sum)
			{
				$this->result = $sum;
			}
			return;
		}
		if ($visit[$index] == true)
		{
			return;
		}
		// Here modified  the value of visited node
		$visit[$index] = true;
		// This is used to iterate nodes edges
		$temp = $this->node[$index]->next;
		while ($temp != NULL)
		{
			$this->findMinPath($source, 
                               $temp->id, $visit, 
                               $sum + ($temp->weight), $count + 1);
			// Visit to next edge
			$temp = $temp->next;
		}
		// Reset the value of visited node status
		$visit[$index] = false;
	}
	public	function travllingSalesmanProblem($source)
	{
		$this->result = PHP_INT_MAX;
		$visit = array_fill(0, $this->size, false);
		// Set initial visited node status 
		for ($i = 0; $i < $this->size; ++$i)
		{
			$visit[$i] = false;
		}
		echo("\n Source node : ".$source);
		$this->findMinPath($source, $source, $visit, 0, 0);
		echo("\n Result : ".$this->result);
	}
}

function main()
{
	// 5 implies the number of nodes in graph
	$g = new Graph(5);
	$g->addEdge(0, 1, 7);
	$g->addEdge(0, 2, 4);
	$g->addEdge(0, 3, 8);
	$g->addEdge(0, 4, 6);
	$g->addEdge(1, 2, 5);
	$g->addEdge(1, 3, 5);
	$g->addEdge(1, 4, 1);
	$g->addEdge(2, 3, 5);
	$g->addEdge(2, 4, 4);
	$g->addEdge(3, 4, 3);
	// print graph element
	$g->printGraph();
	// Test 
	$source = 0;
	$g->travllingSalesmanProblem($source);
}
main();

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
/*
    Node JS Program for
    Travelling salesman problem using backtracking
*/
class AjlistNode
{
	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 Graph
{
	constructor(size)
	{
		// Set value
		this.size = size;
		this.node = Array(size).fill(null);
		this.result = Number.MAX_VALUE;
		this.setData();
	}
	// Set initial node value
	setData()
	{
		if (this.node == null)
		{
			console.log("\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;
		}
	}
	// Add edge of two nodes
	addEdge(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)
			{
				// Self looping situation
				return;
			}
			this.connect(last, start, weight);
		}
		else
		{
			console.log("\nHere Something Wrong");
		}
	}
	printGraph()
	{
		if (this.size > 0 && this.node != null)
		{
			// Print graph ajlist Node value
			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);
					// visit to next edge
					temp = temp.next;
				}
			}
		}
	}
	findMinPath(source, index, visit, sum, count)
	{
		if (source == index && count == this.size)
		{
			// When reached all other vertex and back to source vertex
			if (this.result > sum)
			{
				this.result = sum;
			}
			return;
		}
		if (visit[index] == true)
		{
			return;
		}
		// Here modified  the value of visited node
		visit[index] = true;
		// This is used to iterate nodes edges
		var temp = this.node[index].next;
		while (temp != null)
		{
			this.findMinPath(source, temp.id, 
                             visit, sum + (temp.weight), count + 1);
			// Visit to next edge
			temp = temp.next;
		}
		// Reset the value of visited node status
		visit[index] = false;
	}
	travllingSalesmanProblem(source)
	{
		this.result = Number.MAX_VALUE;
		var visit = Array(this.size).fill(false);
		// Set initial visited node status 
		for (var i = 0; i < this.size; ++i)
		{
			visit[i] = false;
		}
		process.stdout.write("\n Source node : " + source);
		this.findMinPath(source, source, visit, 0, 0);
		process.stdout.write("\n Result : " + this.result);
	}
}

function main()
{
	// 5 implies the number of nodes in graph
	var g = new Graph(5);
	g.addEdge(0, 1, 7);
	g.addEdge(0, 2, 4);
	g.addEdge(0, 3, 8);
	g.addEdge(0, 4, 6);
	g.addEdge(1, 2, 5);
	g.addEdge(1, 3, 5);
	g.addEdge(1, 4, 1);
	g.addEdge(2, 3, 5);
	g.addEdge(2, 4, 4);
	g.addEdge(3, 4, 3);
	// print graph element
	g.printGraph();
	// Test 
	var source = 0;
	g.travllingSalesmanProblem(source);
}
main();

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
import sys
#    Python 3 Program for
#    Travelling salesman problem using backtracking
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 Graph :
	#  Number of Vertices
	def __init__(self, size) :
		#  Set value
		self.size = size
		self.node = [None] * (size)
		self.result = sys.maxsize
		self.setData()
	
	#  Set initial node value
	def setData(self) :
		if (self.node == None) :
			print("\nEmpty Graph")
		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 addEdge(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 looping situation
				return
			
			self.connect(last, start, weight)
		else :
			print("\nHere Something Wrong")
		
	
	def printGraph(self) :
		if (self.size > 0 and self.node != None) :
			index = 0
			#  Print graph ajlist Node value
			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 = "")
					#  visit to next edge
					temp = temp.next
				
				index += 1
			
		
	
	def findMinPath(self, source, index, visit, sum, count) :
		if (source == index and count == self.size) :
			#  When reached all other vertex and back to source vertex
			if (self.result > sum) :
				self.result = sum
			
			return
		
		if (visit[index] == True) :
			return
		
		#  Here modified  the value of visited node
		visit[index] = True
		#  This is used to iterate nodes edges
		temp = self.node[index].next
		while (temp != None) :
			self.findMinPath(source, temp.id, 
                             visit, sum + (temp.weight), count + 1)
			#  Visit to next edge
			temp = temp.next
		
		#  Reset the value of visited node status
		visit[index] = False
	
	def travllingSalesmanProblem(self, source) :
		self.result = sys.maxsize
		visit = [False] * (self.size)
		i = 0
		#  Set initial visited node status 
		while (i < self.size) :
			visit[i] = False
			i += 1
		
		print("\n Source node : ", source, end = "")
		self.findMinPath(source, source, visit, 0, 0)
		print("\n Result : ", self.result, end = "")
	

def main() :
	#  5 implies the number of nodes in graph
	g = Graph(5)
	g.addEdge(0, 1, 7)
	g.addEdge(0, 2, 4)
	g.addEdge(0, 3, 8)
	g.addEdge(0, 4, 6)
	g.addEdge(1, 2, 5)
	g.addEdge(1, 3, 5)
	g.addEdge(1, 4, 1)
	g.addEdge(2, 3, 5)
	g.addEdge(2, 4, 4)
	g.addEdge(3, 4, 3)
	#  print graph element
	g.printGraph()
	#  Test 
	source = 0
	g.travllingSalesmanProblem(source)

if __name__ == "__main__": main()

Output

Adjacency list of vertex  0  :   1   2   3   4
Adjacency list of vertex  1  :   0   2   3   4
Adjacency list of vertex  2  :   0   1   3   4
Adjacency list of vertex  3  :   0   1   2   4
Adjacency list of vertex  4  :   0   1   2   3
 Source node :  0
 Result :  20
#    Ruby Program for
#    Travelling salesman problem using backtracking
class AjlistNode 
	# Define the accessor and reader of class AjlistNode
	attr_reader :id, :weight, :next
	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_reader :data, :next
	attr_accessor :data, :next
	def initialize(data) 
		self.data = data
		self.next = nil
	end

end

class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :size, :node, :result
	attr_accessor :size, :node, :result
	#  Number of Vertices
	def initialize(size) 
		#  Set value
		self.size = size
		self.node = Array.new(size) {nil}
		self.result = (2 ** (0. size * 8 - 2))
		self.setData()
	end

	#  Set initial node value
	def setData() 
		if (self.node == nil) 
			print("\nEmpty Graph", "\n")
		else
 
			index = 0
			while (index < self.size) 
				self.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 (self.node[start].next == nil) 
			self.node[start].next = new_edge
		else
 
			temp = self.node[start].next
			while (temp.next != nil) 
				temp = temp.next
			end

			temp.next = new_edge
		end

	end

	#  Add edge of two nodes
	def addEdge(start, last, weight) 
		if (start >= 0 && start < self.size && 
            last >= 0 && last < self.size && self.node != nil) 
			self.connect(start, last, weight)
			if (start == last) 
				#  Self looping situation
				return
			end

			self.connect(last, start, weight)
		else
 
			print("\nHere Something Wrong", "\n")
		end

	end

	def printGraph() 
		if (self.size > 0 && self.node != nil) 
			index = 0
			#  Print graph ajlist Node value
			while (index < self.size) 
				print("\nAdjacency list of vertex ", index ," :")
				temp = self.node[index].next
				while (temp != nil) 
					print("  ", self.node[temp.id].data)
					#  visit to next edge
					temp = temp.next
				end

				index += 1
			end

		end

	end

	def findMinPath(source, index, visit, sum, count) 
		if (source == index && count == self.size) 
			#  When reached all other vertex and back to source vertex
			if (self.result > sum) 
				self.result = sum
			end

			return
		end

		if (visit[index] == true) 
			return
		end

		#  Here modified  the value of visited node
		visit[index] = true
		#  This is used to iterate nodes edges
		temp = self.node[index].next
		while (temp != nil) 
			self.findMinPath(source, temp.id, 
                             visit, sum + (temp.weight), count + 1)
			#  Visit to next edge
			temp = temp.next
		end

		#  Reset the value of visited node status
		visit[index] = false
	end

	def travllingSalesmanProblem(source) 
		self.result = (2 ** (0. size * 8 - 2))
		visit = Array.new(self.size) {false}
		i = 0
		#  Set initial visited node status 
		while (i < self.size) 
			visit[i] = false
			i += 1
		end

		print("\n Source node : ", source)
		self.findMinPath(source, source, visit, 0, 0)
		print("\n Result : ", self.result)
	end

end

def main() 
	#  5 implies the number of nodes in graph
	g = Graph.new(5)
	g.addEdge(0, 1, 7)
	g.addEdge(0, 2, 4)
	g.addEdge(0, 3, 8)
	g.addEdge(0, 4, 6)
	g.addEdge(1, 2, 5)
	g.addEdge(1, 3, 5)
	g.addEdge(1, 4, 1)
	g.addEdge(2, 3, 5)
	g.addEdge(2, 4, 4)
	g.addEdge(3, 4, 3)
	#  print graph element
	g.printGraph()
	#  Test 
	source = 0
	g.travllingSalesmanProblem(source)
end

main()

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
/*
    Scala Program for
    Travelling salesman problem using backtracking
*/
class AjlistNode(
	// Vertices node key
	var id: Int,
		var weight: Int,
			var next: AjlistNode)
{
	def this(id: Int, weight: Int)
	{
		// Set value of node key
		this(id, weight, null)
	}
}
class Vertices(var data: Int,
	var next: AjlistNode)
{
	def this(data: Int)
	{
		this(data, null)
	}
}
class Graph(
	// Number of Vertices
	var size: Int,
		var node: Array[Vertices],
			var result: Int)
{
	def this(size: Int)
	{
		
		this(size, Array.fill[Vertices](size)(null), Int.MaxValue)
      	// Set value
		this.setData();
	}
	// Set initial node value
	def setData(): Unit = {
		if (node == null)
		{
			println("\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;
		}
	}
	// Add edge of two nodes
	def addEdge(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)
			{
				// Self looping situation
				return;
			}
			connect(last, start, weight);
		}
		else
		{
			println("\nHere Something Wrong");
		}
	}
	def printGraph(): Unit = {
		if (size > 0 && node != null)
		{
			var index: Int = 0;
			// Print graph ajlist Node value
			while (index < size)
			{
				print("\nAdjacency list of vertex " + index + " :");
				var temp: AjlistNode = node(index).next;
				while (temp != null)
				{
					print("  " + node(temp.id).data);
					// visit to next edge
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
	def findMinPath(source: Int, 
                    index: Int, visit: Array[Boolean], 
      sum: Int, count: Int): Unit = {
		if (source == index && count == this.size)
		{
			// When reached all other vertex and back to source vertex
			if (this.result > sum)
			{
				this.result = sum;
			}
			return;
		}
		if (visit(index) == true)
		{
			return;
		}
		// Here modified  the value of visited node
		visit(index) = true;
		// This is used to iterate nodes edges
		var temp: AjlistNode = node(index).next;
		while (temp != null)
		{
			findMinPath(source, temp.id, 
                        visit, sum + (temp.weight),
                        count + 1);
			// Visit to next edge
			temp = temp.next;
		}
		// Reset the value of visited node status
		visit(index) = false;
	}
	def travllingSalesmanProblem(source: Int): Unit = {
		this.result = Int.MaxValue;
		var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
		var i: Int = 0;
		// Set initial visited node status 
		while (i < size)
		{
			visit(i) = false;
			i += 1;
		}
		print("\n Source node : " + source);
		findMinPath(source, source, visit, 0, 0);
		print("\n Result : " + this.result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// 5 implies the number of nodes in graph
		var g: Graph = new Graph(5);
		g.addEdge(0, 1, 7);
		g.addEdge(0, 2, 4);
		g.addEdge(0, 3, 8);
		g.addEdge(0, 4, 6);
		g.addEdge(1, 2, 5);
		g.addEdge(1, 3, 5);
		g.addEdge(1, 4, 1);
		g.addEdge(2, 3, 5);
		g.addEdge(2, 4, 4);
		g.addEdge(3, 4, 3);
		// print graph element
		g.printGraph();
		// Test 
		var source: Int = 0;
		g.travllingSalesmanProblem(source);
	}
}

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20
/*
    Swift 4 Program for
    Travelling salesman problem using backtracking
*/
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(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class Graph
{
	// Number of Vertices
	var size: Int;
	var node: [Vertices?];
	var result: Int;
	init(_ size: Int)
	{
		// Set value
		self.size = size;
		self.node = Array(repeating: nil, count: size);
		self.result = Int.max;
		self.setData();
	}
	// Set initial node value
	func setData()
	{
		if (self.node.count==0)
		{
			print("\nEmpty Graph");
		}
		else
		{
			var index: Int = 0;
			while (index < self.size)
			{
				self.node[index] = Vertices(index);
				index += 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;
		}
	}
	// Add edge of two nodes
	func addEdge(_ start: Int, _ last: Int, _ weight: Int)
	{
		if (start >= 0 && start < self.size && 
            last >= 0 && last < self.size && self.node.count  != 0)
		{
			self.connect(start, last, weight);
			if (start == last)
			{
				// Self looping situation
				return;
			}
			self.connect(last, start, weight);
		}
		else
		{
			print("\nHere Something Wrong");
		}
	}
	func printGraph()
	{
		if (self.size > 0 && self.node.count  != 0)
		{
			var index: Int = 0;
			// Print graph ajlist Node value
			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: "");
					// visit to next edge
					temp = temp!.next;
				}
				index += 1;
			}
		}
	}
	func findMinPath(_ source: Int, _ index: Int, 
                     _ visit: inout[Bool], _ sum: Int, _ count: Int)
	{
		if (source == index && count == self.size)
		{
			// When reached all other vertex and back to source vertex
			if (self.result > sum)
			{
				self.result = sum;
			}
			return;
		}
		if (visit[index] == true)
		{
			return;
		}
		// Here modified  the value of visited node
		visit[index] = true;
		// This is used to iterate nodes edges
		var temp: AjlistNode? = self.node[index]!.next;
		while (temp  != nil)
		{
			self.findMinPath(source, temp!.id, 
                             &visit, sum + (temp!.weight), count + 1);
			// Visit to next edge
			temp = temp!.next;
		}
		// Reset the value of visited node status
		visit[index] = false;
	}
	func travllingSalesmanProblem(_ source: Int)
	{
		self.result = Int.max;
		var visit: [Bool] = Array(repeating: false, count: self.size);
		var i: Int = 0;
		// Set initial visited node status 
		while (i < self.size)
		{
			visit[i] = false;
			i += 1;
		}
		print("\n Source node : ", source, terminator: "");
		self.findMinPath(source, source, &visit, 0, 0);
		print("\n Result : ", self.result, terminator: "");
	}
}
func main()
{
	// 5 implies the number of nodes in graph
	let g: Graph = Graph(5);
	g.addEdge(0, 1, 7);
	g.addEdge(0, 2, 4);
	g.addEdge(0, 3, 8);
	g.addEdge(0, 4, 6);
	g.addEdge(1, 2, 5);
	g.addEdge(1, 3, 5);
	g.addEdge(1, 4, 1);
	g.addEdge(2, 3, 5);
	g.addEdge(2, 4, 4);
	g.addEdge(3, 4, 3);
	// print graph element
	g.printGraph();
	// Test 
	let source: Int = 0;
	g.travllingSalesmanProblem(source);
}
main();

Output

Adjacency list of vertex  0  :   1   2   3   4
Adjacency list of vertex  1  :   0   2   3   4
Adjacency list of vertex  2  :   0   1   3   4
Adjacency list of vertex  3  :   0   1   2   4
Adjacency list of vertex  4  :   0   1   2   3
 Source node :  0
 Result :  20
/*
    Kotlin Program for
    Travelling salesman problem using backtracking
*/
class AjlistNode
{
	// Vertices node key
	var id: Int;
	var weight: Int;
	var next: AjlistNode ? ;
	constructor(id: Int, weight: Int)
	{
		// Set value of node key
		this.id = id;
		this.weight = weight;
		this.next = null;
	}
}
class Vertices
{
	var data: Int;
	var next: AjlistNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class Graph
{
	// Number of Vertices
	var size: Int;
	var node: Array < Vertices ? > ;
	var result: Int;
	constructor(size: Int)
	{
		// Set value
		this.size = size;
		this.node = Array(size)
		{
			null
		};
		this.result = Int.MAX_VALUE;
		this.setData();
	}
	// Set initial node value
	fun setData(): Unit
	{
		if (this.size <= 0)
		{
			println("\nEmpty Graph");
		}
		else
		{
			var index: Int = 0;
			while (index < this.size)
			{
				this.node[index] = Vertices(index);
				index += 1;
			}
		}
	}
	// Connect two nodes
	fun connect(start: Int, last: Int, weight: Int): Unit
	{
		val new_edge: AjlistNode = AjlistNode(last, weight);
		if (this.node[start]?.next == null)
		{
			this.node[start]?.next = new_edge;
		}
		else
		{
			var temp: AjlistNode ? = this.node[start]?.next;
			while (temp?.next != null)
			{
				temp = temp.next;
			}
			temp?.next = new_edge;
		}
	}
	// Add edge of two nodes
	fun addEdge(start: Int, last: Int, weight: Int): Unit
	{
		if (start >= 0 && start < this.size && 
            last >= 0 && last < this.size && this.size > 0)
		{
			this.connect(start, last, weight);
			if (start == last)
			{
				// Self looping situation
				return;
			}
			this.connect(last, start, weight);
		}
		else
		{
			println("\nHere Something Wrong");
		}
	}
	fun printGraph(): Unit
	{
		if (this.size > 0 )
		{
			var index: Int = 0;
			// Print graph ajlist Node value
			while (index < this.size)
			{
				print("\nAdjacency list of vertex " + index + " :");
				var temp: AjlistNode ? = this.node[index]?.next;
				while (temp != null)
				{
					print("  " + this.node[temp.id]?.data);
					// visit to next edge
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
	fun findMinPath(source: Int, index: Int, 
                    visit: Array < Boolean > , sum: Int, count: Int): Unit
	{
		if (source == index && count == this.size)
		{
			// When reached all other vertex and back to source vertex
			if (this.result > sum)
			{
				this.result = sum;
			}
			return;
		}
		if (visit[index] == true)
		{
			return;
		}
		// Here modified  the value of visited node
		visit[index] = true;
		// This is used to iterate nodes edges
		var temp: AjlistNode ? = this.node[index]?.next;
		while (temp != null)
		{
			this.findMinPath(source, temp.id, 
          	visit, sum + (temp.weight), count + 1);
			// Visit to next edge
			temp = temp.next;
		}
		// Reset the value of visited node status
		visit[index] = false;
	}
	fun travllingSalesmanProblem(source: Int): Unit
	{
		this.result = Int.MAX_VALUE;
		val visit: Array < Boolean > = Array(this.size)
		{
			false
		};
		var i: Int = 0;
		// Set initial visited node status 
		while (i < this.size)
		{
			visit[i] = false;
			i += 1;
		}
		print("\n Source node : " + source);
		this.findMinPath(source, source, visit, 0, 0);
		print("\n Result : " + this.result);
	}
}
fun main(args: Array < String > ): Unit
{
	// 5 implies the number of nodes in graph
	val g: Graph = Graph(5);
	g.addEdge(0, 1, 7);
	g.addEdge(0, 2, 4);
	g.addEdge(0, 3, 8);
	g.addEdge(0, 4, 6);
	g.addEdge(1, 2, 5);
	g.addEdge(1, 3, 5);
	g.addEdge(1, 4, 1);
	g.addEdge(2, 3, 5);
	g.addEdge(2, 4, 4);
	g.addEdge(3, 4, 3);
	// print graph element
	g.printGraph();
	// Test 
	val source: Int = 0;
	g.travllingSalesmanProblem(source);
}

Output

Adjacency list of vertex 0 :  1  2  3  4
Adjacency list of vertex 1 :  0  2  3  4
Adjacency list of vertex 2 :  0  1  3  4
Adjacency list of vertex 3 :  0  1  2  4
Adjacency list of vertex 4 :  0  1  2  3
 Source node : 0
 Result : 20


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.

New Comment







© 2021, kalkicode.com, All rights reserved