# Christofides Algorithm C Program

## C Program For Christofides Algorithm for TSP

Learn How To Implement Christofides Algorithm in C Programming for solving Travelling Salesman Problem (TSP). Here, you will get a complete details of the Algorithm for solving Christofides Problem.

#### What is Christofides Algorithm Travelling Salesman Problem?

Christofides Algorithm is an **approximation algorithm** to find the optimum and most efficient solution to the **Travelling Salesman Problem**. The Christofides Heuristic approach for solving TSP Algorithm is an approximation algorithm that offers the solution for Travelling Salesman Problem via Christofides Heuristic Algorithm within the range of 3/2 of the optimal solution length.

This is the best approximation ratio for solving the Travelling Salesman Problem using Christofides Solution Algorithm in C Programming. The Christofides Approximation Algorithm, therefore, helps to achieve 3/2 approximation to the Travelling Salesperson Problem Algorithm

#### Need of Heuristics Approach

- No Perfect Estimation on the Quality of the Solution
- Guaranteed to Execute in Polynomial Time
- Generates Intuitive Algorithms

#### Need of Approximation Algorithms

- Guaranteed to Execute in Polynomial Time
- Finds Better Solution within 1 – 2% of the Optimal Solution to the problem

#### Christofides Algorithm

Let G be a complete graph with a set of vertices v and a function w makes every edge with a non-negative value for its real weight.

- Create a
**Minimum Spanning Tree**T from the Graph G. - O is a set of vertices having an Odd Degree in the Minimum Spanning Tree.
- Find
**Minimum Weight**perfect matching M in the abstracted subgraph from O. - Build a
**Connected Multigraph**H where each vertex has even degree by combining edges of M and T. - Develop and
**Eulerian Circuit**in the graph H. - Construct the
**Hamiltonian Circuit**by excluding repeated vertices from the circuit of the previous step.

#### C Program For Christofides Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | function Minimum_Spanning_Tree(G = (vertices, edges)) for vertices in vertices do value[vertices] <-- infinity parent_element[vertices] <-- NULL insert vertices into Queue end for value[0] <-- 0 while !Queue.empty() do vertices <-- Queue.removerticeseMin() for x adjacent to vertices do if x ∈ Queue and weight(x, vertices) < value[x] then parent_element[x] <-- vertices end if value[vertices] <-- weight(x, vertices) end for end while end function |

In case you get any Compilation Errors or any doubts in this Christofides Algorithm Implementation in C Programming, let us know about it in the Comment Section below. Find more information about **Christofides Solution Algorithm** on Wikipedia.

After so many searches gone in vain, I finally found out a good explanation and an algorithm in C programming for Christofides algorithm. Thanks.

The travelling salesman problem can’t be approximated better than 1.0081 in polynomial time.

You can get 1-approximation can be obtained by adapting a truncated version of Held and Karp’s exact O∗(2n)O∗(2n) where n is the number of cities or points.