A E D B C at 250 cost
Since there are only 5 nodes, it's perfectly acceptable to brute force the solution.
Since the travel costs are symmetrical, the number of solutions is always divisible by 2 (each solution can be reversed)
This example has exactly 2 solutions, no less and no more.
Starting at A makes sense, but doesn't have to. In this example you could also start at C.
Branch and bound is my algorithm of choice in case the number of nodes gets too great, but isn't necessary here.
#include <stdio.h>
#include <stdlib.h>
#define INF 999 /* not max_int to prevent overflow */
#define START 0 /* fixed start because symmetric travel costs */
#define NODES "ABCDE"
#define SIZE 5
int main(void) {
int matrix[SIZE][SIZE] = {
{INF,100,125,100, 75},
{100,INF, 50, 75,125},
{125, 50,INF,100,125},
{100, 75,100,INF, 50},
{ 75,125,125, 50,INF}
};
int b, c, d, e, w;
int cheapest = INF * INF;
for(b = 0; b < SIZE; b++) {
if(START == b) {
continue;
}
for(c = 0; c < SIZE; c++) {
if(c == START || c == b) {
continue;
}
for(d = 0; d < SIZE; d++) {
if(d == START || d == b || d == c) {
continue;
}
for(e = 0; e < SIZE; e++) {
if(e == START || e == b || e == c || e == d) {
continue;
}
w = matrix[START][b] + matrix[b][c] + matrix[c][d] + matrix[d][e];
if(w < cheapest) {
cheapest = w;
printf("%c %c %c %c %c = %d\n", NODES[START], NODES[b], NODES[c], NODES[d], NODES[e], w);
}
}
}
}
}
return EXIT_SUCCESS;
}
Fuck performance. All hail nested loops.
