Hello there. I stumbled upon your codings for my Algorithm Design course assignment. I tried to run it but I seem to not understand the output generated by the coding. Here's the output that I got:
Input:
tsp([[1, 1], [2, 5], [8, 0]])
Output:
Graph: {0: {1: 4.123105625617661, 2: 7.0710678118654755}, 1: {0: 4.123105625617661, 2: 7.810249675906654}, 2: {0: 7.0710678118654755, 1: 7.810249675906654}} MSTree: [(0, 1, 4.123105625617661), (0, 2, 7.0710678118654755)] Odd vertexes in MSTree: [1, 2] Minimum weight matching: [(0, 1, 4.123105625617661), (0, 2, 7.0710678118654755), (1, 2, 7.810249675906654)] Eulerian tour: [1, 0, 2, 1] Result path: [1, 2, 1, 1] Result length of the path: 15.620499351813308
Isn't Christofides Algorithm supposed to generated the shortest path between all the nodes? And why are the resulting path nodes repeated (three '1's). Would appreciate some clarification from your behalf!
Hello there. I stumbled upon your codings for my Algorithm Design course assignment. I tried to run it but I seem to not understand the output generated by the coding. Here's the output that I got:
Input:
tsp([[1, 1], [2, 5], [8, 0]])Output:
Graph: {0: {1: 4.123105625617661, 2: 7.0710678118654755}, 1: {0: 4.123105625617661, 2: 7.810249675906654}, 2: {0: 7.0710678118654755, 1: 7.810249675906654}} MSTree: [(0, 1, 4.123105625617661), (0, 2, 7.0710678118654755)] Odd vertexes in MSTree: [1, 2] Minimum weight matching: [(0, 1, 4.123105625617661), (0, 2, 7.0710678118654755), (1, 2, 7.810249675906654)] Eulerian tour: [1, 0, 2, 1] Result path: [1, 2, 1, 1] Result length of the path: 15.620499351813308Isn't Christofides Algorithm supposed to generated the shortest path between all the nodes? And why are the resulting path nodes repeated (three '1's). Would appreciate some clarification from your behalf!