Trying to discover both First and Second Shortests paths but returns only last vertex

I'm trying to make the following code return the First Shortest Path then removing it so it can calculate the Second Shortest Path. So far it only returns the last node which in this case is 10 but should return something similar to 1-2-4-6-9-10 for one of the paths (this not the right solution just an example).

Note: Trying to make this code work without anyone teaching Matlab, it's all purely discussed with colleagues/searched on google so sorry for any bad/weird syntaxe usage

matrix = [0  3  6  8  2  inf  inf  inf  inf  inf;          3  0  5  7  9   1  inf  inf  inf  inf;          6  5  0  5  8   10  2  inf  inf  inf;          8  7  5  0  4   9   14  3  inf  inf;          2  9  8  4  0   5   12  15  4  inf;          inf  1  10  9  5  0   10  20  25  5;          inf  inf  2  14  12  10  0   12  30  35;          inf  inf  inf  3  15  20  12  0   25  40;          inf  inf  inf  inf  4  25  30  25  0   45;          inf  inf  inf  inf  inf  5  35  40  45  0];
% Input:
start = 1;
ending = 10;




% Initialize variables
n = size(matrix,1); % number of vertices
d = inf(1,n); % distance array
d(start) = 0; % starting vertex distance = 0
prev = zeros(1,n); % predecessor array
S = false(1, n); % set of labeled vertices
S(start) = true;

if all(d == inf)
    disp('The graph is disconnected')
    return
end

for i = 1:size(matrix,1)
    for j = 1:size(matrix,2)
        if matrix(i,j) == 0
            matrix(i,j) = inf;
        end
    end
end




% First shortest path
matrix = matrix + matrix';
%matrix(matrix == inf) = 0;
%matrix(matrix > 0) = inf;

while S(ending) == false
    % Select vertex with smallest distance
    [v] = min(d(~S));
    v = find(~S,1,'first');
    S(v) = true; % "permanently" label vertex

    % Update distances and predecessors of neighbors
    for u = find(matrix(v,:)~=inf)
        if d(v) + matrix(v,u) < d(u) && matrix(v,u) <= inf

            d(u) = d(v) + matrix(v,u);
            prev(u) = v;
        end
    end
end

% Output first shortest path
path = ending;
while prev(path(end)) ~= 0
    path = [path, prev(path(end))];
end
fprintf('First Shortest Path: ')
for i = length(path):-1:1
    fprintf('%d ', path(i))
end
fprintf('\n')



% Second shortest path
for i = 2:length(path)
    matrix(path(i), path(i-1)) = inf; % remove the edge from first path
end

d = inf(1,n); % distance array
d(start) = 0; % starting vertex distance = 0
prev = zeros(1,n); % predecessor array
S = false(1, n); % set of labeled vertices
S(start) = true;

% Repeat the process to find the second shortest path
while S(ending) == false
    % Select vertex with smallest distance
    [v] = min(d(~S)); 
    v = find(~S,1,'first');
    S(v) = true; % "permanently" label vertex
    % Update distances and predecessors of neighbors
    for u = find(matrix(v,:)~=inf)
        if d(v) + matrix(v,u) < d(u) && matrix(v,u) <= inf

            d(u) = d(v) + matrix(v,u);
            prev(u) = v;
        end
    end
end

% Output second shortest path
path = [ending];
while prev(path(1)) ~= 0
    path = [prev(path(1)),path];
end
fprintf('Second Shortest Path: ')
for i = 1:length(path)
    fprintf('%d ', path(i))
end
fprintf('\n')

Answer 1

[Rajeev]

Hi,

It looks like the if condition to update the distances of neighbours is never executed because the 'v' you selected is incorrect.

One approach is: Instead of just assigning binary states to the vertices (visited and unvisited), we can assign three states:

• Unvisited: Have not reached this vertex yet,
• Visiting: Current active vertex whose neighbours will be travesed in the current interation
• Visited: Vertex whose all neighbours have been visited.

Then, you can modify the code like given below:

% 0 = unvisited
% 1 = visiting
% 2 = visited
S = zeros(1,n); % set of labeled vertices
% the root/source node will be explored first
S(start) = 1;
if all(d == inf)
    disp('The graph is disconnected')
    return
end

for i = 1:size(matrix,1)
    for j = 1:size(matrix,2)
        if matrix(i,j) == 0
            matrix(i,j) = inf;
        end
    end
end

% First shortest path
matrix = matrix + matrix';

while S(ending) == false
    % Select vertex(visiting) with the smallest distance 
    min_d = min(d(S==1));
    v = find(d==min_d);
    % Update distances and predecessors of neighbors
    for u = find(matrix(v,:)~=inf)
        if d(v) + matrix(v,u) < d(u) && matrix(v,u) <= inf
            % Each neighbour node state is updated from unvisited to
            % visiting
            S(u) = 1;
            d(u) = d(v) + matrix(v,u);
            prev(u) = v;
        end
    end
    % After exloring all neighbours, the current node is marked visited.
    S(v) = 2;
end

Similarly, you can modify the code for second shortest path.