clear all
clc

% Choose between two input possibilities: Coordinates in Excel file
% 'Test'from different cities or insert distance matrix direct here in script

% %%%Input coordinates of the cities via Excel file
% data = xlsread('Test.xlsx',1)
% dist = dist(data(:,2:5)') % how many coordinates are necessary to describe the location from one city
% dist(dist==0) = inf

%%%Input directly distance matrix
% Input information
A = [inf, 4, 12, 7, 4, 1, 2, 8, 4, 6, 7, 12, 3, 5, 20];
B = [5, inf, 20, 18, 6, 3, 4, 8, 9, 23, 1, 12, 5, 4, 9];
C = [11, 5, inf, 6, 1, 5, 6, 8, 7, 12, 31, 5, 1, 14, 5];
D = [10, 2, 3, inf, 5, 7, 8, 8, 6, 21, 4, 7, 5, 5, 1];
E = [1, 2, 6, 9, inf, 9, 10, 8, 45, 12, 11, 5, 6, 2, 11];
F = [17, 7, 6, 5, 11, inf, 12, 8, 63, 1, 2, 3, 12, 4, 8];
G = [11, 8, 3, 9, 3, 5, inf, 4, 6, 8, 1, 3, 12, 4, 8];
H = [12, 14, 2, 5, 4, 8, 4, inf, 12, 4, 1, 23, 7, 4, 56];
I = [4, 1, 2, 8, 4, 6, 7, 12, 3, inf, 7, 5, 6, 12, 14];
J = [6, 1, 5, 6, 8, 7, 12, 31, 5, 1, inf, 12, 1, 2, 6];
K = [7, 8, 8, 6, 21, 4, 7, 5, 5, 1, 11, inf, 13, 1, 2];
L = [1, 6, 1, 5, 6, 8, 7, 12, 8, 9, 10, 12, inf, 7, 5];
M = [8, 4, 6, 7, 12, 3, 8, 4, 6, 7, 12, 3, inf, 14, 15];
N = [21, 4, 7, 5, 5, 1, 21, 4, 7, 5, 5, 1,13, inf, 1];
O = [4, 12, 7, 4, 1, 2, 8, 4, 6, 7, 12, 3, 5, 20, inf];
% Generate distance matrix
dist = [A; B; C; D; E; F; G; H; I; J; K; L; M; N; O]

% Initalization
MaxCity = length(dist);
i = 1;
n = 1;
Parentcity = 1;
Childcity = 0;

% Array
costarray = zeros(MaxCity, 2);
wayarray = zeros(MaxCity, 2);
wayarray(1,:)=[1 0]

% Reduktion und Kosten der ParentCity
row_reduction = min(dist, [], 2);
row_reduction(isinf(row_reduction)) = 0;
M_row_reduced = dist - row_reduction;

column_reduction = min(M_row_reduced);
M_working = M_row_reduced - column_reduction;
M_working(isnan(M_working)) = inf;
M_reduced = M_working;
costparent = sum(row_reduction) + sum(column_reduction);

for n = [n:1:MaxCity]              % levels der baumstruktur

for i = [i:1:MaxCity]; % childcity i= childcity
    if i == Parentcity ||i==1
        cost = inf;

    else
        M_working= M_reduced;
        M_working(Parentcity, :) = inf;
        M_working(:, i) = inf;
        M_working(i, Parentcity) = inf;
        M_working(Parentcity,i) = 0; %!!!!

        row_reduction = min(M_working, [], 2);
        row_reduction(isinf(row_reduction)) = 0;
        M_row_reduced = M_working - row_reduction;

        column_reduction = min(M_row_reduced);
        M_working = M_row_reduced - column_reduction;
        M_working(isnan(M_working)) = inf;


        cost = costparent+ sum(row_reduction) + sum(column_reduction)+ M_reduced(Parentcity, i);
    end
    costarray(i, :) = [i,cost];
end
i = 1;

% minimum der cost array finden
[M, I] = min(costarray);
childcity = I(1, 2);
costparent = M(1, 2);
wayarray(n +1, :) = [childcity, dist(wayarray(n,1),childcity)]; %änderung!!

% nimm childcity, reduziere matrix für diese
M_working=M_reduced;
M_working(Parentcity, childcity) = inf;
M_working(:, childcity) = inf;
M_working(childcity, Parentcity) = inf;
M_working(Parentcity,childcity) = 0; %!!!!

row_reduction = min(M_working, [], 2);
row_reduction(isinf(row_reduction)) = 0;
M_row_reduced = M_working - row_reduction;

column_reduction = min(M_row_reduced);
M_working = M_row_reduced - column_reduction;
M_working(isnan(M_working)) = inf;

M_reduced=M_working;

Parentcity = childcity;
end
wayarray(n+1,2)=dist(wayarray(n,1),1)
gesamtlaenge=sum(wayarray(:,2))