- 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.
Output First Shortest Path and Second Shortest Path
2 views (last 30 days)
Show older comments
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')
0 Comments
Answers (1)
Amith
on 11 Aug 2024
Hi Carlos,
To achieve the above result you could refer to the below linked file exchange for finding the shortest length path -
To achieve the second shortest path using djkstras you might have to modify the graph in the following way:
Hope this helps!
0 Comments
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!