#include #include #include #include #include "graph.h" // we keep track of the best path so far globally unsigned int best_cost = INT_MAX; int* best_path = NULL; // run through all permutations void permute(struct graph* graph, int* array, int start, int end) { // if this is the end of the permutation, consider this path if (start == end) { unsigned int total_cost = 0; // add up this route for (int i = 0; i < (graph->size - 1); i++) { // get the cost of this leg int leg = get_cost(graph, array[i], array[i + 1]); total_cost = total_cost + leg; } // add end city back to start total_cost = total_cost + get_cost(graph, array[graph->size - 1], array[0]); //printf("Found a path with cost %d.\n", total_cost); // check if this is the best so far if (total_cost < best_cost) { best_cost = total_cost; for (int i = 0; i < graph->size; i++) { best_path[i] = array[i]; } } } // otherwise we are not at the end of this permutation yet else { // for each node in the list for (int i = start; i <= end; i++) { // swap this with the start int temp = array[start]; array[start] = array[i]; array[i] = temp; // permute all after the start permute(graph, array, start + 1, end); // swap it back temp = array[start]; array[start] = array[i]; array[i] = temp; } } } void shortestTour(struct graph* graph) { // make an array of the nodes int* nodes = malloc(sizeof(int) * graph->size); for (int i = 0; i < graph->size; i++) { nodes[i] = i; } // run through all permutations permute(graph, nodes, 1, graph->size - 1); // print the results printf("The tour should go through:\n"); for (int i = 0; i < graph->size; i++) { printf("%s, ", get_label(graph, best_path[i])); } printf("and back to %s.\n", get_label(graph, best_path[0])); printf("For a total cost of %d.\n", best_cost); } int main(int argc, char** argv) { if (argc < 2) { printf("Please pass an input file!\n"); return 0; } // open the file and read the input size FILE* file = fopen(argv[1], "r"); int size; fscanf(file, "%d", &size); // create a graph with struct graph graph; init_graph(&graph, size); // read the node labels for (int i = 0; i < size; i++) { char label[64]; fscanf(file, "%s", label); set_label(&graph, i, label); } // read the edge information for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { int cost; fscanf(file, "%d", &cost); insert_edge(&graph, i, j, cost); } } // make space for the best path best_path = malloc(sizeof(int) * size); // compute the shortest tour shortestTour(&graph); }