CODEWITHSUNDEEP
graphgraph-theorygraph-algorithm
Sid Prasad
Sid Prasad

Reputation: 157

Circular tour of a graph

Given a directed graph with N nodes and M edges, you need to find the minimum cost circular tour of the graph, i.e., starting at a particular city X and ending at that same city.

What is the most efficient way to do this for both the following cases:

  1. No weights on the edges
  2. Weighted edges (Wi for ith edge)
  3. The above two cases but with the condition that each city can be visited no more than one time. (Apart from the first city). If this is not possible then output will be -1.

Thanks in advance!

Upvotes: 1

Views: 174

Answers (1)

Cahit Gungor
Cahit Gungor

Reputation: 1497

1. No weights on edges.

If there is no cost on edges, actually all circuits become equal in which all costs are 0. Reasonably, if it is implicitly said that the cost is, actually, the minimum number of hops, consequently any circuit satisfying the conditions above is also equivalent. Then, the question is finding a circuit, namely a Hamiltonian Circuit or Hamiltonian Cycle. To find out a Hamiltonian Circuit in a graph is NP-complete.

There are n! possible routes. A brute force approach has a runtime complexity of O(n!), where n represents the number of edges.

One of the best algorithms existing is in here with simulations and code.

2. Weighted edges (Wi for ith edge)

When graph has weighted edges, the problem becomes the well known TSP (Travelling Salesman Problem), which is an NP-hard problem. There exists a confusion in the community, around TSP complexity. You have to make distinction between, TSP-Optimize and TSP-Decide.

TSP-Optimize is NP-hard.

TSP-Decide is NP-complete.

For detailed explanations check those resources 1 2. You can find a discussion in here.

You are asked to implement TSP-Optimize.

- Dynamic Programming

Bellman–Held–Karp algorithm. You can find the pseudo code in here. Runtime Complexity: O(2n n2), where n represents the number of edges.

Although, there exists other solution technics, with Divide-and-Conquer or Greedy approaches, they are not optimal.

Upvotes: 1

Related Questions