% shortest.m 

% load the weighted adjacency matrix as a matrix variable A
directedgraph;

% read n, the number of nodes in the graph
n = size(A,1);

% define which node is giong to be used as a source
s = 1;

% use this as a surrogate of infinity distance
infinity=100000;

% initialize distance vector to infinity except for the source s
dist = infinity*ones(n,1);
dist(s) = 0;

% initialize the set of permanent labels with a single entry s
permanent = [s;];

% initialize the shortest path tree as an empty set 
shortestpathtree = [];

% parentnode(i) is a node in permanent label set that is included in the current shortest
% paths to node i
parentnode = zeros(n,1);

% repeat adding nodes into permanent label one by one
for idx=1:n-1
    % distance update
    for candidate=1:n
        if (length(find(candidate==permanent))==0) 
            % for each candidate node that is not in the permanent label 
            % compute and update the distance of each candidate to the
            % source as in Dijkstra algorithm
            parent = parentnode(candidate);
            for k=1:size(permanent,1)
                perm = permanent(k);
                if (A(perm,candidate)~=0) 
                    if (dist(candidate)>dist(perm)+A(perm,candidate)) 
                        dist(candidate) = dist(perm)+A(perm,candidate);
                        parent = perm;
                    end
                end
            end
            parentnode(candidate) = parent;
        end
    end
    % node selection
    temp_dist = dist;
    temp_dist(permanent)=infinity;
    [min_value min_index] = min(temp_dist);
    % add the minimum distance cadidate node to the permanent set
    permanent = [permanent; min_index;];
    % add the edge between the candidate node and the edge connecting the
    % candidate node to the permanent set via the shortest path to the
    % shortest path tree
    shortestpathtree = [shortestpathtree; parentnode(min_index) min_index;];
end

% display the length of a shortest path from the source s to all nodes
fprintf('The length of the shortest path from %i to all nodes \n',s);
display(dist);

% display the shortest path tree
fprintf('The shortest path tree and the weights on the edges\n');
for i=1:n-1
    fprintf('(%i,%i)\t%i\n',shortestpathtree(i,1),shortestpathtree(i,2),A(shortestpathtree(i,1),shortestpathtree(i,2)));
end

%% solution (a)
fprintf('Length of the shortest path from 1 to 18 = %i\n',dist(18));

%% solution (b)
directedgraph;
s = 1;
dist = infinity*ones(n,1);
dist(s) = 0;
permanent = [s;];
for idx=1:n-1
    % distance update
    for candidate=1:n
        if (length(find(candidate==permanent))==0) 
            for k=1:size(permanent,1)
                perm = permanent(k);
                if (A(perm,candidate)~=0) 
                    dist(candidate) = min([ dist(candidate), dist(perm)+A(perm,candidate) ]);
                end
            end
        end
    end
    % node selection
    temp_dist = dist;
    temp_dist(permanent)=infinity;
    [min_value min_index] = min(temp_dist);
    permanent = [permanent; min_index;];
end
dist1=dist;
s = 19;
dist = infinity*ones(n,1);
dist(s) = 0;
permanent = [s;];
for idx=1:n-1
    % distance update
    for candidate=1:n
        if (length(find(candidate==permanent))==0) 
            for k=1:size(permanent,1)
                perm = permanent(k);
                if (A(perm,candidate)~=0) 
                    dist(candidate) = min([ dist(candidate), dist(perm)+A(perm,candidate) ]);
                end
            end
        end
    end
    % node selection
    temp_dist = dist;
    temp_dist(permanent)=infinity;
    [min_value min_index] = min(temp_dist);
    permanent = [permanent; min_index;];
end
dist2=dist;
fprintf('Length of the shortest path from 1 to 18 that does pass through 19 = %i\n',dist1(19)+dist2(18));

%% solution (c)
directedgraph;
s=1;
A(9,:)=0;
A(:,9)=0;
% initialize distance vector to infinity except for the source s
dist = infinity*ones(n,1);
dist(s) = 0;

% initialize the set of permanent labels with a single entry s
permanent = [s;];

% initialize the shortest path tree as an empty set 
shortestpathtree = [];

% parentnode(i) is a node in permanent label set that is included in the current shortest
% paths to node i
parentnode = zeros(n,1);

% repeat adding nodes into permanent label one by one
for idx=1:n-1
    % distance update
    for candidate=1:n
        if (length(find(candidate==permanent))==0) 
            % for each candidate node that is not in the permanent label 
            % compute and update the distance of each candidate to the
            % source as in Dijkstra algorithm
            parent = parentnode(candidate);
            for k=1:size(permanent,1)
                perm = permanent(k);
                if (A(perm,candidate)~=0) 
                    if (dist(candidate)>dist(perm)+A(perm,candidate)) 
                        dist(candidate) = dist(perm)+A(perm,candidate);
                        parent = perm;
                    end
                end
            end
            parentnode(candidate) = parent;
        end
    end
    % node selection
    temp_dist = dist;
    temp_dist(permanent)=infinity;
    [min_value min_index] = min(temp_dist);
    % add the minimum distance cadidate node to the permanent set
    permanent = [permanent; min_index;];
    % add the edge between the candidate node and the edge connecting the
    % candidate node to the permanent set via the shortest path to the
    % shortest path tree
    shortestpathtree = [shortestpathtree; parentnode(min_index) min_index;];
end
fprintf('Length of the shortest path from 1 to 18 that does not pass through 9 = %i\n',dist(18));

%% solution (d) 
directedgraph;
a = 5;
b = 6;
s = 1;
dist = infinity*ones(n,1);
dist(s) = 0;
permanent = [s;];
for idx=1:n-1
    % distance update
    for candidate=1:n
        if (length(find(candidate==permanent))==0) 
            for k=1:size(permanent,1)
                perm = permanent(k);
                if (A(perm,candidate)~=0) 
                    dist(candidate) = min([ dist(candidate), dist(perm)+A(perm,candidate) ]);
                end
            end
        end
    end
    % node selection
    temp_dist = dist;
    temp_dist(permanent)=infinity;
    [min_value min_index] = min(temp_dist);
    permanent = [permanent; min_index;];
end
dist1=dist;
s = b;
dist = infinity*ones(n,1);
dist(s) = 0;
permanent = [s;];
for idx=1:n-1
    % distance update
    for candidate=1:n
        if (length(find(candidate==permanent))==0) 
            for k=1:size(permanent,1)
                perm = permanent(k);
                if (A(perm,candidate)~=0) 
                    dist(candidate) = min([ dist(candidate), dist(perm)+A(perm,candidate) ]);
                end
            end
        end
    end
    % node selection
    temp_dist = dist;
    temp_dist(permanent)=infinity;
    [min_value min_index] = min(temp_dist);
    permanent = [permanent; min_index;];
end
dist2=dist;
fprintf('Length of the shortest path from 1 to 18 that does pass through (5,6) = %i\n',dist1(a)+dist2(18)+A(a,b));

