How can I get all the existing shortest paths between two single nodes for graph
19 次查看(过去 30 天)
显示 更早的评论
I konw that there are many functions can compute the distance between two nodes, and there are some functions can return the shortest path between two nodes, however, I find all the functions seem only return the first shortest path between two nodes, but I want to find a way to get all the existing shortest paths between two single nodes for graph. For instance, if we have a graph: (1,2), (1,3), (2,4), (3,4), when I query the shortest path between 1 and 4, it should return (1,2,4) and (1,3,4). Thanks!
0 个评论
回答(3 个)
Bruno Luong
2020-8-22
编辑:Bruno Luong
2020-8-24
Here is the code base on Bellman Ford algorithm which provides ALL shortest paths from a single node to ALL other nodes
s = [1 1 1 1 2 2 2 2 2 8 8 12 14 14 1 14];
t = [3 5 4 2 6 10 7 9 8 11 12 13 7 6 8 15];
G = graph(s,t);
[d,spath] = BellmanFord(G, 1); % function bellow
for k=1:length(spath)
spk = spath{k};
fprintf('shortest path from 1 to %d is(are):\n', k)
for i=1:length(spk)
fprintf('\t%s\n', mat2str(spk{i}));
end
end
Put this function in an mfile BellmanFord.m
function [d, spath] = BellmanFord(arg1, arg2)
% d = BellmanFord(A, start) OR
% d = BellmanFord(G, start)
%
% [d, spath] = BellmanFord(...)
%
% BellmanFord shortest paths
%
% INPUTS:
% A: (N x N) symmtric ajadcent matrix or
% G: graph/digraph object with N nodes
% start; interger in [1,N] start node
% OUTPUTS:
% d: (N x 1): array contains distance vector from start-node to all nodes
% spath: (N x 1) cell array. All shortest paths.
% For dest in [1,N] spath{dest} is a a row-cell contains all
% shortest paths (array of nodes) from start-node to dest-node.
%
% See also: graph, digraph, TestAllShortestPaths
%
% Author: brunoluong at yahoo dot findmycountry
if isa(arg1,'graph') || isa(arg1,'digraph')
G = arg1;
if ismultigraph(G)
edges = table2array(G.Edges);
ij = edges(:,1:2);
w = edges(:,3);
n = max(ij,[],'all');
A = accumarray(ij, w, [n,n], @min, 0, true);
if isa(arg1,'graph')
A = triu(A,1).'+A;
end
else
A = G.adjacency('weight');
end
else
A = arg1;
end
if nargin < 2
start = 1; % starting node
else
start = arg2;
end
A = A.';
n = size(A,1);
start = max(min(start,n),1);
% initialize distance matrix
d = inf(n,1);
du = 0;
i = start;
if nargout < 2
% only distance is requested
while true
d(i) = du;
[i, j, dij] = find(A(:,i));
if isempty(i)
break
end
[du, p] = sort(du(j)+dij);
[i, p] = sort(i(p)); % here we requires stable sorting, which is the case with MATLAB
b = [true; diff(i,1,1)>0];
i = i(b);
du = du(p(b));
b = du < d(i);
i = i(b);
du = du(b);
end
else
% shortest paths requested
prev = cell(n,1);
neig = inf(1,n);
for c = 0:n-1
d(i) = du;
neig(i) = c;
jprev = i;
[i, j, dij] = find(A(:,jprev));
if isempty(i)
break
end
I = [i, du(j)+dij, jprev(j)];
I = sortrows(I, [1 2]);
dI = diff([0 0; I(:,1:2)],1,1) ~= 0;
change = find(dI(:,1)|dI(:,2));
Ic = I(change,:);
b = dI(change,1) & (Ic(:,2) <= d(Ic(:,1)));
lgt = diff([change; size(dI,1)+1],1,1);
I = I(repelem(b, lgt),:);
if isempty(I)
break
end
lgtk = lgt(b);
istart = cumsum([1; lgtk]);
istop = istart(2:end)-1;
istart(end) = [];
% keep track the previous visit nodes
% doing like jprev = mat2cell(I(:,3), lgtk, 1); without overhead
jprev = cell(size(istart));
j = I(:,3);
for k=1:size(jprev)
jprev{k} = j(istart(k):istop(k));
end
i = I(istart,1);
du = I(istart,2);
neq = du < d(i);
if all(neq) % optimization by not bother with CELLFUN
prev(i) = jprev;
else
prev(i(neq)) = jprev(neq);
eq = ~neq;
ieq = i(eq);
prev(ieq) = cellfun(@union, prev(ieq), jprev(eq), 'unif', 0);
end
end
% Second past to build shortest paths
spath = cell(size(prev));
spath{start} = {start};
[neig, k] = sort(neig);
k = k(2:find(isfinite(neig),1,'last'));
for n = k
spath{n} = cellfun(@(p) [p,n], cat(1, spath{prev{n}}), 'unif', 0);
end % for-loop
end % if of shortest paths branch
end % BellmanFord
10 个评论
Rub Ron
2020-8-24
s = [1 1 2 3 1 4 5];
t = [2 2 3 4 4 5 6];
G = graph(s,t);
G.Edges.Weight = [1 1 3 1 1 1 1]';
[~,spath] = BellmanFord(G,1);
spath{6}{:}
Output: (perhaps a unique is missing)
ans =
1 4 5 6
ans =
1 2 3 4 5 6
ans =
1 4 5 6
ans =
1 2 3 4 5 6
ans =
1 4 5 6
ans =
1 2 3 4 5 6
ans =
1 4 5 6
ans =
1 2 3 4 5 6
Bruno Luong
2020-8-24
Yes, I change VERTCAT with UNION in CELLFUN statement and it fixes the redundancy.
spath{6}{:}
ans =
1 4 5 6
ans =
1 2 3 4 5 6
Koushik Kureti
2020-3-5
Hello Yang Feiming,
You can use graph class in MATLAB, which has a shortest path method
If it is a directed graph, you can use the digraph class instead.
If you want to find out shortest paths between all nodes in the graph, then the following link helps: https://www.mathworks.com/help/matlab/ref/graph.distances.html
0 个评论
Walter Roberson
2020-8-21
Populate a column vector with a list of all of the source nodes to be considered. Call this L.
Loop:
Set NewL to empty.
Loop examining each row in L. Extract the last column of the row, which will be a node number, N. Look up the connections (output connections in case of a digraph) that N has, and remove from that set all nodes that already exist in the current row of L. Now for each remaining connected node, add the current row followed by the connected node, as an entry at the end of NewL; if you have run out of connected nodes that do not already appear in the current row then you would not be adding anything to NewL.
Once you are done examining all rows in L, set L = NewL.
Select all rows of L that end in any of the destination nodes. If there are none, then continue looping; otherwise, the outer loop.
End of outer loop.
Output list the list of rows in L that end in any of the destination nodes.
This algorithm can have multiple start nodes and multiple destination nodes, and will find all of the shortest paths of equal length between any of the start nodes and any of the destination nodes.
This algorithm is a "breadth first search" and can be implemented in terms of the bfsearch() operation.
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!