Output First Shortest Path and Second Shortest Path

As the question above says I want to find the first and second shortest path of a matrix, my current problem is that the only output that I get is the last vertex but I want the full path in the example of the code that I have the starting Node is 1 and the ending node is 10, so the output should be for example 1 - 3 - 4 - 9 - 10. After finding the First Path I want to discard it and find the next shortest path.

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 || S(start) == 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 = [start];

while prev(path(end)) ~= 0
    path = [path, prev(path(end))];
end
path = fliplr(path);
fprintf('First Shortest Path: ')
for i = 1:length(path)
    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(end)) ~= 0
path = [prev(path(end)),path];
end
path = fliplr(path);
fprintf('Second Shortest Path: ');
for i = 1:length(path)
fprintf('%d ', path(i))
end
fprintf('\n')

Answer 1

[Amith]

Hi Carlos,

To achieve the above result you could refer to the below linked file exchange for finding the shortest length path -

https://www.mathworks.com/matlabcentral/fileexchange/36140-dijkstra-algorithm

To achieve the second shortest path using djkstras you might have to modify the graph in the following way:

• Remove each edge in the shortest path.
• Now find the shortest path again.
• Finally compare and return the shortest path among them as the second shortest path from source to destination.

Hope this helps!