manaav

manaav / Travelingsalesman / 1.1.0

README.md

Overview

The Renu Traveling Salesman's Problem algorithm finds optimal TSP path in an undirected graph in polynomial time. The algorithm is written in Python. Though the algorithm is desiged to work for N number of nodes, this particular version supports graphs upto 100 nodes with weight ranging from 1 to 100.

Applicable Scenarios and Problems

Usage

Input

The program takes graph as input in the form of two dimensional List. For example, below is the pattern of input for a graph of 5 nodes/vertices.

{ "graph": [[0, 33, 88, 74, 23], [33, 0, 99, 5, 17], [88, 99, 0, 23, 48], [74, 5, 23, 0, 64], [23, 17, 48, 64, 0]] }

Note: Max nodes/vertices accepted is 100 with edge weight ranging from 1 to 100, weight 0 signifies nodes are not connected.

Output

On success, the program returns a dictionary with following members.

  1. error_string: Error reason if failed to find TSP, empty if successful.
  2. result: contains 1 for success, 0 for failure
  3. tsp: List of vertices of TSP path in traversal order, empty list on failure
  4. tsp_cost: Total TSP path cost

Examples

Input graph with 5 nodes (1, 2, 3, 4, 5) as given below: { "graph": [[0, 33, 88, 74, 23], [33, 0, 99, 5, 17], [88, 99, 0, 23, 48], [74, 5, 23, 0, 64], [23, 17, 48, 64, 0]] }

Will return the following dictionary: {"error_string":"","result":1,"tsp":[1,3,4,2,5,1],"tsp_cost":156}