Is it possible to implement the Christofides algorithm for an directed Graph?Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to itself). But the weights of the edges, don't necessarily have do be the same in both ways (unsymmetrical).For Example you think of a Street Map, in which there are a lot of oneway streets.We now want to find an approximation for the traveling salesman tour through all the vertices.First of all the Christoffides algorithm is not defined for such an TSP, because the Minimum Spanning Tree ist not defined for an directed Graph.But still we start the algorithm by finding the optimum branching with Edmonds algorithm to the start point of the tour as the root.Then we find a minimal perfect matching for the branching, so that it becomes an Eulerian graph. This will happen with the Hungarian algorithm, wich finds an minimal matching so that every vertex in the branching has afterwords the same amount of edges coming in an out.In the last step we find the euler tour and optimize the tour by taking shortcuts.I have to questions:Is the way I want to implement the algorithm right, or did I made a mistake and it can't workIf it works, is it still bounded bei 1,5 of the optimal solution for the tsp?
Christofides algorithm for directed graph
tsp;matching;minimization