Output First Shortest Path and Second Shortest Path

3 次查看（过去 30 天）
Carlos
Carlos 2023-1-17
回答： Amith 2024-8-11
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')

请先登录，再回答此问题。

回答（1 个）

Amith
Amith 2024-8-11
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!

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by